結果
| 問題 |
No.5002 stick xor
|
| コンテスト | |
| ユーザー |
 hakomo
|
| 提出日時 | 2018-05-26 20:36:20 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 987 ms / 1,000 ms |
| コード長 | 9,387 bytes |
| コンパイル時間 | 34,935 ms |
| 実行使用メモリ | 2,388 KB |
| スコア | 47,051 |
| 最終ジャッジ日時 | 2018-05-26 20:36:56 |
|
ジャッジサーバーID （参考情報） |
judge9 / |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 32 |
ソースコード
#include <algorithm>
#include <array>
#include <chrono>
#include <cmath>
#include <iostream>
#include <random>
#include <vector>
using namespace std;
#define U(v) cerr << #v << ": " << (v) << endl
class timer {
vector<timer> timers;
int n = 0;
public:
double limit = 0.98;
double t = 0;
timer() {}
timer(int size) : timers(size) {}
bool elapses() const {
return time() - t > limit;
}
void measure() {
t = time() - t;
++n;
}
void measure(char id) {
timers[id].measure();
}
void print() {
if (n % 2)
measure();
for (int i = 0; i < 128; ++i) {
if (timers[i].n)
cerr << (char)i << ' ' << timers[i].t << 's' << endl;
}
cerr << " " << t << 's' << endl;
}
static double time() {
#ifdef LOCAL
return __rdtsc() / 3.3e9;
#else
return chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now().time_since_epoch()).count() / 1000.0;
#endif
}
} timer(128);
class {
//unsigned y = 2463534242;
unsigned y = random_device()();
public:
unsigned next() {
return y ^= (y ^= (y ^= y << 13) >> 17) << 5;
}
int next(int b) {
return next() % b;
}
int next(int a, int b) {
return next(b - a) + a;
}
double nextDouble(double b = 1) {
return b * next() / 4294967296.0;
}
double nextDouble(double a, double b) {
return nextDouble(b - a) + a;
}
int operator() (int b) {
return next(b);
}
} rando;
constexpr int N = 60;
constexpr int K = 500;
int L[K];
bool A[N][N];
unsigned long long ls[N];
unsigned long long cs[N];
vector<array<int, 5>> states, bestStates;
int score, bestScore;
double ths[128];
inline void flip(const array<int, 5>& r, bool up) {
if (r[2] != 1) {
ls[r[1]] ^= ((1ull << r[2]) - 1) << r[0];
if (up) {
unsigned long long mask = 1ull << r[1];
for (int x = r[0]; x < r[0] + r[2]; ++x)
cs[x] ^= mask;
}
} else {
cs[r[0]] ^= ((1ull << r[3]) - 1) << r[1];
if (up) {
unsigned long long mask = 1ull << r[0];
for (int y = r[1]; y < r[1] + r[3]; ++y)
ls[y] ^= mask;
}
}
}
int main(int argc, char** argv) {
timer.measure();
{
int k;
cin >> k >> k;
for (int i = 0; i < K; ++i)
cin >> L[i];
char s[N + 1];
for (int y = 0; y < N; ++y) {
cin >> s;
for (int x = 0; x < N; ++x)
A[y][x] = s[x] == '1';
}
}
//{
// mt19937 mt(atoi(argv[1]));
// for (int i = 0; i < K; ++i)
// L[i] = mt() % 25 + 1;
// for (int y = 0; y < N; ++y)
// for (int x = 0; x < N; ++x)
// A[y][x] = mt() % 2 == 1;
//}
for (int y = 0; y < N; ++y) {
for (int x = 0; x < N; ++x) {
if (A[y][x]) {
ls[y] |= 1ull << x;
cs[x] |= 1ull << y;
} else {
--score;
}
}
}
vector<int> a1, a2;
for (int i = 0; i < K; ++i) {
if (L[i] > 2) {
int x = rando.next(N - L[i] + 1);
int y = rando.next(N);
if (rando.next(2)) {
states.emplace_back(array<int, 5>{ x, y, L[i], 1, i });
} else {
states.emplace_back(array<int, 5>{ y, x, 1, L[i], i });
}
flip(states.back(), true);
} else {
(L[i] == 1 ? a1 : a2).emplace_back(i);
score += L[i];
}
}
for (int y = 0; y < N; ++y)
score += N - (int)__builtin_popcountll(ls[y]);
bestScore = score;
bestStates = states;
int ni = -1;
vector<array<int, 3>> ne;
for (int i = 0; i < (int)states.size(); ++i)
for (int j = 0; j < 2; ++j)
for (int k = 0; k < N; ++k)
ne.emplace_back(array<int, 3>{ i, j, k });
random_shuffle(ne.begin(), ne.end(), rando);
bool hf = false;
for (int iter = -1; ; ) {
if ((++iter & 0x1fff) == 0) {
double p = 1 - (timer.time() - timer.t) / timer.limit;
if (p < 0) {
//U(iter);
break;
} else if (!hf && p < 0.4) {
hf = true;
int n = (int)ne.size();
for (int i = 0; i < n; ++i) {
auto& r = states[ne[i][0]];
for (int m = max(0, 5 - (r[2] != 1 ? r[2] : r[3])); m--; )
ne.emplace_back(ne[i]);
}
random_shuffle(ne.begin(), ne.end(), rando);
}
constexpr double InitialHeat = 0.8;
constexpr double FinalHeat = 1e-9;
double heat = p * (InitialHeat - FinalHeat) + FinalHeat;
for (int i = 0; i < 128; ++i)
ths[i] = log((i + 0.5) / 128) * heat;
random_shuffle(ths, ths + 128, rando);
}
if (++ni == ne.size()) ni = 0;
auto& r = states[ne[ni][0]];
int l, diff;
bool up = false;
if (r[2] != 1) {
l = r[2];
unsigned long long mask = ((1ull << r[2]) - 1) << r[0];
ls[r[1]] ^= mask;
diff = l - (int)__builtin_popcountll(ls[r[1]] & mask) * 2;
if (!ne[ni][1]) {
mask = 1ull << r[1];
for (int x = r[0]; x < r[0] + r[2]; ++x)
cs[x] ^= mask;
up = true;
}
} else {
l = r[3];
unsigned long long mask = ((1ull << r[3]) - 1) << r[1];
cs[r[0]] ^= mask;
diff = l - (int)__builtin_popcountll(cs[r[0]] & mask) * 2;
if (ne[ni][1]) {
mask = 1ull << r[0];
for (int y = r[1]; y < r[1] + r[3]; ++y)
ls[y] ^= mask;
up = true;
}
}
long long th = (long long)floor((ths[iter & 127] - diff + l) / 2);
static vector<array<int, 5>> candidates;
candidates.clear();
if (ne[ni][1]) {
int y = ne[ni][2];
long long b = __builtin_popcountll(ls[y] & (1ull << l) - 1);
unsigned long long l1 = ls[y];
unsigned long long l2 = ls[y] >> l;
for (int x = l; ; ++x) {
if (b > th)
candidates.emplace_back(array<int, 5>{ x - l, y, l, 1, (int)b });
if (x == N) break;
b -= (l1 & 1) - (l2 & 1);
l1 >>= 1;
l2 >>= 1;
}
} else {
int x = ne[ni][2];
long long b = __builtin_popcountll(cs[x] & (1ull << l) - 1);
unsigned long long c1 = cs[x];
unsigned long long c2 = cs[x] >> l;
for (int y = l; ; ++y) {
if (b > th)
candidates.emplace_back(array<int, 5>{ x, y - l, 1, l, (int)b });
if (y == N) break;
b -= (c1 & 1) - (c2 & 1);
c1 >>= 1;
c2 >>= 1;
}
}
if (candidates.empty()) {
flip(r, up);
continue;
}
auto& c = candidates.size() == 1 ? candidates[0] : candidates[rando.next((int)candidates.size())];
score += c[4] * 2 - l + diff;
if (!up) {
if (r[2] != 1) {
unsigned long long mask = 1ull << r[1];
for (int x = r[0]; x < r[0] + r[2]; ++x)
cs[x] ^= mask;
} else {
unsigned long long mask = 1ull << r[0];
for (int y = r[1]; y < r[1] + r[3]; ++y)
ls[y] ^= mask;
}
}
r[0] = c[0];
r[1] = c[1];
r[2] = c[2];
r[3] = c[3];
flip(r, true);
if (bestScore < score) {
bestScore = score;
bestStates = states;
}
}
score = bestScore;
states.swap(bestStates);
for (auto& r : states)
for (int y = r[1]; y < r[1] + r[3]; ++y)
for (int x = r[0]; x < r[0] + r[2]; ++x)
A[y][x] ^= 1;
for (int y = 0; y < N; ++y) {
for (int x = 0; x < N; ++x) {
if (y && A[y][x] && A[y - 1][x] && a2.size()) {
A[y][x] = A[y - 1][x] = false;
states.emplace_back(array<int, 5>{ x, y - 1, 1, 2, a2.back() });
a2.pop_back();
}
if (x && A[y][x] && A[y][x - 1] && a2.size()) {
A[y][x] = A[y][x - 1] = false;
states.emplace_back(array<int, 5>{ x - 1, y, 2, 1, a2.back() });
a2.pop_back();
}
}
}
for (int y = 0; y < N; ++y) {
for (int x = 0; x < N; ++x) {
if (A[y][x] && a1.size()) {
states.emplace_back(array<int, 5>{ x, y, 1, 1, a1.back() });
a1.pop_back();
}
}
}
sort(states.begin(), states.end(), [](const array<int, 5>& a, const array<int, 5>& b) {
return a[4] < b[4];
});
for (auto& r : states)
cout << r[1] + 1 << ' ' << r[0] + 1 << ' ' << r[1] + r[3] << ' ' << r[0] + r[2] << endl;
//cout << "# " << atoi(argv[1]) << ',' << score << endl;
return 0;
}