結果
| 問題 |
No.5002 stick xor
|
| コンテスト | |
| ユーザー |
 hakomo
|
| 提出日時 | 2018-05-29 19:29:31 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 985 ms / 1,000 ms |
| コード長 | 14,128 bytes |
| コンパイル時間 | 35,354 ms |
| 実行使用メモリ | 1,820 KB |
| スコア | 52,535 |
| 最終ジャッジ日時 | 2018-05-29 19:30:08 |
|
ジャッジサーバーID （参考情報） |
judge6 / |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| 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
constexpr int dx[] = { 1, 0, -1, 0 };
constexpr int dy[] = { 0, 1, 0, -1 };
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;
struct Rectangle {
bool vertical;
int x, y, length, id;
Rectangle() {}
Rectangle(bool vertical, int x, int y, int length, int id)
: vertical(vertical), x(x), y(y), length(length), id(id) {}
};
struct Line {
bool vertical;
int y;
long long line;
Line() {}
Line(bool vertical, int y) : vertical(vertical), y(y) {}
};
constexpr int N = 60;
constexpr int K = 500;
int L[K];
bool A[N][N];
long long board[2][N];
vector<int> lineToIndicies[2][N];
vector<Rectangle> states, bestStates;
int score, bestScore;
inline void flip(const Rectangle& r) {
board[r.vertical][r.y] ^= ((1ll << r.length) - 1) << r.x;
long long mask = 1ll << r.y;
for (int x = r.x; x < r.x + r.length; ++x)
board[!r.vertical][x] ^= mask;
}
inline void flip2(const Rectangle& r, unsigned i) {
board[r.vertical][r.y] ^= ((1ll << r.length) - 1) << r.x;
if (i - r.x < (unsigned)r.length)
board[!r.vertical][i] ^= 1ll << r.y;
}
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';
}
}
for (int y = 0; y < N; ++y) {
for (int x = 0; x < N; ++x) {
if (A[y][x]) {
board[0][y] |= 1ll << x;
board[1][x] |= 1ll << y;
} else {
--score;
}
}
}
vector<int> a1, a2;
{
pair<int, int> a[K];
for (int i = 0; i < K; ++i)
a[i] = { L[i], i };
sort(rbegin(a), rend(a));
for (auto& p : a) {
if (p.first > 2) {
long long b = -1 << 30;
array<int, 3> n;
for (int i = 0; i < 2; ++i) {
for (int y = 0; y < N; ++y) {
for (int x = 0; x < N - p.first + 1; ++x) {
long long s = __builtin_popcountll(board[i][y] & ((1ll << p.first) - 1) << x);
if (b < s) {
b = s;
n = { i, x, y };
}
}
}
}
lineToIndicies[n[0]][n[2]].emplace_back((int)states.size());
states.emplace_back(!!n[0], n[1], n[2], p.first, p.second);
flip(states.back());
} else {
(p.first == 1 ? a1 : a2).emplace_back(p.second);
score += p.first;
}
}
}
for (int y = 0; y < N; ++y)
score += N - (int)__builtin_popcountll(board[0][y]);
vector<array<Line, 2>> ne;
int ni = -1;
for (int i = 1; i < N * 2; ++i) {
for (int j = 0; j < i; ++j) {
ne.emplace_back(array<Line, 2>{ Line{ !!(i & 1), i >> 1 }, { !!(j & 1), j >> 1 } });
if (ne.back()[0].vertical)
swap(ne.back()[0], ne.back()[1]);
}
}
random_shuffle(ne.begin(), ne.end(), rando);
double heat = 0;
for (int iter = -1; ; ) {
if ((++iter & 0x7ff) == 0) {
double p = 1 - (timer.time() - timer.t) / timer.limit;
if (p < 0) break;
constexpr double InitialHeat = 0.6;
constexpr double FinalHeat = 1e-9;
heat = 1 / (p * (InitialHeat - FinalHeat) + FinalHeat);
}
if (++ni == ne.size()) ni = 0;
auto& lines = ne[ni];
bool parallel = lines[0].vertical == lines[1].vertical;
static vector<int> indicies;
static vector<Rectangle> rectangles;
indicies.clear();
rectangles.clear();
lines[0].line = board[lines[0].vertical][lines[0].y];
lines[1].line = board[lines[1].vertical][lines[1].y];
int s0, s1;
{
auto& p = lineToIndicies[lines[0].vertical][lines[0].y];
auto& q = lineToIndicies[lines[1].vertical][lines[1].y];
s0 = (int)p.size();
s1 = (int)q.size();
for (int n = min(3, s0 + s1); n--; ) {
int i = rando.next(s0 + s1);
if (i < s0) {
indicies.emplace_back(p[i]);
flip2(states[p[i]], parallel ? -1 : lines[1].y);
swap(p[i], p[--s0]);
} else {
i -= (int)s0;
indicies.emplace_back(q[i]);
flip2(states[q[i]], parallel ? -1 : lines[0].y);
swap(q[i], q[--s1]);
}
}
}
for (int i : indicies) {
auto& r = states[i];
long long bn = -1 << 30;
rectangles.emplace_back(r);
auto& br = rectangles.back();
for (auto& l : lines) {
long long line = board[l.vertical][l.y];
long long mask = (1ll << r.length) - 1;
for (int x = r.length; x <= N; x += 2) {
long long n = __builtin_ctzll(line);
x += (int)n;
line >>= n;
n = __builtin_popcountll(line & mask);
if (bn < n) {
bn = n;
br.vertical = l.vertical;
br.y = l.y;
br.x = min(N, x) - r.length;
if (bn == r.length) break;
}
line >>= 2;
}
if (bn == r.length) break;
}
flip2(br, parallel ? -1 : lines[!br.vertical].y);
}
for (int last = -1; ; ) {
bool updated = false;
for (auto& r : rectangles) {
long long bn = board[r.vertical][r.y] & ((1ll << r.length) - 1) << r.x;
if (bn == 0)
if (last == r.id) break;
else continue;
long long cn = bn = r.length - __builtin_popcountll(bn);
flip2(r, parallel ? -1 : lines[!r.vertical].y);
for (auto& l : lines) {
long long line = board[l.vertical][l.y];
long long mask = (1ll << r.length) - 1;
for (int x = r.length; x <= N; x += 2) {
long long n = __builtin_ctzll(line);
x += (int)n;
line >>= n;
n = __builtin_popcountll(line & mask);
if (bn < n) {
bn = n;
r.vertical = l.vertical;
r.y = l.y;
r.x = min(N, x) - r.length;
}
line >>= 2;
}
}
flip2(r, parallel ? -1 : lines[!r.vertical].y);
if (bn != cn) {
updated = true;
last = r.id;
} else if (last == r.id) break;
}
if (!updated) break;
}
int diff = (int)(__builtin_popcountll(lines[0].line) + __builtin_popcountll(lines[1].line)
- (!parallel && lines[0].line >> lines[1].y & 1)
- __builtin_popcountll(board[lines[0].vertical][lines[0].y])
- __builtin_popcountll(board[lines[1].vertical][lines[1].y])
+ (!parallel && board[lines[0].vertical][lines[0].y] >> lines[1].y & 1));
if (rando.nextDouble() < exp(diff * heat)) {
score += diff;
lineToIndicies[lines[0].vertical][lines[0].y].resize(s0);
lineToIndicies[lines[1].vertical][lines[1].y].resize(s1);
lines[0].line = lines[1].line = 0;
for (int i = 0; i < (int)indicies.size(); ++i) {
auto& r = states[indicies[i]];
for (int j = 0; j < 2; ++j) {
int k = r.vertical == lines[1].vertical && r.y == lines[1].y;
lines[k].line ^= ((1ll << r.length) - 1) << r.x;
if (!parallel && (unsigned)lines[!r.vertical].y - r.x < (unsigned)r.length)
lines[k].line ^= 1ll << lines[!r.vertical].y;
if (j == 0)
r = rectangles[i];
else
lineToIndicies[r.vertical][r.y].emplace_back(indicies[i]);
}
}
for (auto& l : lines) {
long long mask = 1ll << l.y;
while (l.line) {
long long x = __builtin_ctzll(l.line);
board[!l.vertical][x] ^= mask;
l.line ^= 1ll << x;
}
}
if (bestScore < score) {
bestScore = score;
bestStates = states;
}
} else {
board[lines[0].vertical][lines[0].y] = lines[0].line;
board[lines[1].vertical][lines[1].y] = lines[1].line;
}
}
score = bestScore;
states.swap(bestStates);
for (auto& r : states) {
if (r.vertical) {
for (int x = r.x; x < r.x + r.length; ++x)
A[x][r.y] ^= 1;
} else {
for (int x = r.x; x < r.x + r.length; ++x)
A[r.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(true, y - 1, x, 2, a2.back());
a2.pop_back();
} else if (x && A[y][x] && A[y][x - 1] && a2.size()) {
A[y][x] = A[y][x - 1] = false;
states.emplace_back(false, x - 1, y, 2, a2.back());
a2.pop_back();
}
}
}
for (int y = 0; y < N; ++y) {
for (int x = 0; x < N; ++x) {
if (A[y][x]) continue;
for (int i = 1; i < 4; ++i) {
int x2 = x + dx[i];
int y2 = y + dy[i];
if (x2 < 0 || N <= x2 || y2 < 0 || N <= y2 || !A[y2][x2]) continue;
for (int j = 0; j < i; ++j) {
int x3 = x + dx[j];
int y3 = y + dy[j];
if (x3 < 0 || N <= x3 || y3 < 0 || N <= y3 || !A[y3][x3] || a2.size() < 2) continue;
A[y2][x2] = A[y3][x3] = false;
score -= 2;
if (i % 2)
states.emplace_back(true, min(y, y2), x, 2, a2.back());
else
states.emplace_back(false, min(x, x2), y, 2, a2.back());
a2.pop_back();
if (j % 2)
states.emplace_back(true, min(y, y3), x, 2, a2.back());
else
states.emplace_back(false, min(x, x3), y, 2, a2.back());
a2.pop_back();
break;
}
}
}
}
score -= (int)a2.size() * 2;
for (int y = 0; y < N && a2.size(); ++y) {
for (int x = 0; x < N && a2.size(); ++x) {
if (y && A[y][x] != A[y - 1][x]) {
for (; a2.size(); a2.pop_back()) {
A[y][x] ^= 1;
A[y - 1][x] ^= 1;
states.emplace_back(true, y - 1, x, 2, a2.back());
}
}
if (x && A[y][x] != A[y][x - 1]) {
for (; a2.size(); a2.pop_back()) {
A[y][x] ^= 1;
A[y][x - 1] ^= 1;
states.emplace_back(false, x - 1, y, 2, a2.back());
}
}
}
}
for (int y = 0; y < N; ++y) {
for (int x = 0; x < N; ++x) {
if (A[y][x] && a1.size()) {
states.emplace_back(false, x, y, 1, a1.back());
a1.pop_back();
}
}
}
sort(states.begin(), states.end(), [](const Rectangle& a, const Rectangle& b) {
return a.id < b.id;
});
for (auto& r : states) {
if (r.vertical)
cout << r.x + 1 << ' ' << r.y + 1 << ' ' << r.x + r.length << ' ' << r.y + 1 << endl;
else
cout << r.y + 1 << ' ' << r.x + 1 << ' ' << r.y + 1 << ' ' << r.x + r.length << endl;
}
return 0;
}