結果
問題 | No.5002 stick xor |
ユーザー |
![]() |
提出日時 | 2018-05-28 01:58:14 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 955 ms / 1,000 ms |
コード長 | 5,398 bytes |
コンパイル時間 | 34,444 ms |
実行使用メモリ | 1,660 KB |
スコア | 31,519 |
最終ジャッジ日時 | 2018-05-28 01:58:50 |
ジャッジサーバーID (参考情報) |
judge8 / |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 32 |
ソースコード
#include <bits/stdc++.h>// make_tuple emplace_back next_permutation push_back make_pair second first// setprecision#if MYDEBUG#include "lib/cp_debug.hpp"#else#define DBG(...) ;#endifusing LL = long long;constexpr LL LINF = 334ll << 53;constexpr int INF = 15 << 26;constexpr LL MOD = 1E9 + 7;namespace Problem {using namespace std;//レプリカ交換モンテカルロ//軸方向の移動//長さの交換//回転、平行移動//の三層でやるstruct Rec {int dir, // direction(0,horizontal, 1:vertical),y, x; // coordinate left-upper corner};uint32_t x = 123456789, y = 362436069, z = 521288629, w = 88675123;uint32_t xor128() {uint32_t t = x ^ (x << 11);x = y;y = z;z = w;return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));}class Solver {public:int n, k;const int ub = 25;vector<int> len;vector<vector<int>> grid, flip, len_id;vector<Rec> rec;random_device rnd;mt19937 mt;chrono::system_clock::time_point start = chrono::system_clock::now();Solver(LL n, LL k): n(n),k(k),len(k),grid(n, vector<int>(n)),len_id(ub + 1),rec(k),mt(rnd()){};void calc_SA() {double temperature = 10.0;int q, d, x, y;int score = -evaluate(grid, rec), max_score = score;DBG(score)for (int i = 0; i < k; ++i) {d = xor128() % 2;y = xor128() % n;x = xor128() % (n - len[i] + 1);if (d == 1) swap(x, y);add_rectangle(i, d, y, x, true);}score += evaluate(grid, rec);max_score = score;vector<Rec> ans = rec;DBG(score)while (!time_limit()) {q = xor128() % k;d = xor128() % 2;y = xor128() % n;x = xor128() % (n - len[q] + 1);if (d == 1) swap(x, y);auto tmp = rec[q];double diff =remove_rectangle(q, true) + add_rectangle(q, d, y, x, true);double diff2 = remove_rectangle(q, true) +add_rectangle(q, tmp.dir, tmp.y, tmp.x, true);if ((double)xor128() / (double)(1ll << 32) <exp(diff / temperature)) {remove_rectangle(q, true) + add_rectangle(q, d, y, x, true);DBG(score, diff)score += diff;if (score > max_score) {max_score = score;ans = rec;}}temperature = (1000 - chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now() - start).count()) /100;}cerr << score << ' ' << max_score << endl;}int evaluate(vector<vector<int>> &a, vector<Rec> &r) {int ret = n * n;for (int i = 0; i < n; ++i) {for (int j = 0; j < n; ++j) {ret -= a[i][j];}}return ret;}int remove_rectangle(int i, bool ex = false) {int ret = 0;int yy = rec[i].y;int xx = rec[i].x;for (int j = 0; j < len[i]; ++j) {ret += (grid[yy][xx]);if (ex) grid[yy][xx] ^= 1;if (rec[i].dir == 0) {xx++;} else {yy++;}}return 2 * ret - len[i];}int add_rectangle(int i, int dir, int y, int x, bool ex = false) {if (ex) rec[i] = {dir, y, x};int ret = 0;for (int j = 0; j < len[i]; ++j) {ret += (grid[y][x]);if (ex) grid[y][x] ^= 1;if (dir == 0) {x++;} else {y++;}}return 2 * ret - len[i];}void input() {for (int i = 0; i < k; ++i) {cin >> len[i];}for (int i = 0; i < n; ++i) {for (int j = 0; j < n; ++j) {char tmp;cin >> tmp;grid[i][j] = tmp - '0';}}}void output() {for (int i = 0; i < k; ++i) {if (rec[i].dir == 0) {cout << rec[i].y + 1 << ' ' << rec[i].x + 1 << ' '<< rec[i].y + 1 << ' ' << rec[i].x + len[i] << "\n";} else {cout << rec[i].y + 1 << ' ' << rec[i].x + 1 << ' '<< rec[i].y + len[i] << ' ' << rec[i].x + 1 << "\n";}}}void solve() {input();uniform_int_distribution<int> seed(0, 100);int loop = seed(mt);for (int i = 0; i < loop; ++i) {xor128();}calc_SA();output();}bool time_limit(double thres = 0.95) {double t = chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now() - start).count() /1000.0;return t > thres;}}; // namespace Problem} // namespace Problemint main() {std::cin.tie(0);std::ios_base::sync_with_stdio(false);long long n = 0, k;std::cin >> n >> k;Problem::Solver sol(n, k);sol.solve();return 0;}