結果
問題 | No.5002 stick xor |
ユーザー |
![]() |
提出日時 | 2018-05-26 13:29:21 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 955 ms / 1,000 ms |
コード長 | 5,915 bytes |
コンパイル時間 | 33,702 ms |
実行使用メモリ | 2,380 KB |
スコア | 46,323 |
最終ジャッジ日時 | 2018-05-26 13:29:56 |
ジャッジサーバー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) << endlclass timer {vector<timer> timers;int n = 0;public:double limit = 0.95;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 LOCALreturn __rdtsc() / 3.3e9;#elsereturn 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];vector<array<int, 5>> states, bestStates;int score, bestScore;double ths[128];inline void flip(const array<int, 5>& r) {if (r[2] != 1) {for (int x = r[0]; x < r[0] + r[2]; ++x)A[r[1]][x] ^= 1;} else {for (int y = r[1]; y < r[1] + r[3]; ++y)A[y][r[0]] ^= 1;}}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[61];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 i = 0; i < K; ++i) {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());}score = bestScore = 0;bestStates = states;int ni = -1;vector<array<int, 3>> ne;for (int i = 0; i < K; ++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);for (int iter = -1; ; ) {if ((++iter & 0xfff) == 0) {double p = 1 - (timer.time() - timer.t) / timer.limit;if (p < 0) {//U(iter);break;}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 = 0;if (r[2] != 1) {l = r[2];for (int x = r[0]; x < r[0] + r[2]; ++x)diff += (A[r[1]][x] ^= 1) ? -1 : 1;} else {l = r[3];for (int y = r[1]; y < r[1] + r[3]; ++y)diff += (A[y][r[0]] ^= 1) ? -1 : 1;}int th = (int)floor((ths[iter & 127] - diff + l) / 2);static vector<array<int, 5>> candidates;candidates.clear();if (ne[ni][1]) {int y = ne[ni][2];int b = 0;for (int x = 0; x < l; ++x)b += A[y][x];for (int x = 0; ; ++x) {if (b > th)candidates.emplace_back(array<int, 5>{ x, y, l, 1, b * 2 - l + diff });if (x + l == N) break;b -= A[y][x] - A[y][x + l];}} else {int x = ne[ni][2];int b = 0;for (int y = 0; y < l; ++y)b += A[y][x];for (int y = 0; ; ++y) {if (b > th)candidates.emplace_back(array<int, 5>{ x, y, 1, l, b * 2 - l + diff });if (y + l == N) break;b -= A[y][x] - A[y + l][x];}}if (candidates.empty()) {flip(r);continue;}auto& c = candidates.size() == 1 ? candidates[0] : candidates[rando.next((int)candidates.size())];score += c[4];r[0] = c[0];r[1] = c[1];r[2] = c[2];r[3] = c[3];flip(r);if (bestScore < score) {bestScore = score;bestStates = states;}}score = bestScore;states.swap(bestStates);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;}