結果
問題 | No.5002 stick xor |
ユーザー |
![]() |
提出日時 | 2018-05-26 01:40:04 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 973 ms / 1,000 ms |
コード長 | 6,066 bytes |
コンパイル時間 | 35,831 ms |
実行使用メモリ | 1,632 KB |
スコア | 41,301 |
最終ジャッジ日時 | 2018-05-26 01:40:45 |
ジャッジサーバーID (参考情報) |
judge6 / |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 32 |
ソースコード
#pragma GCC optimize ("O3")#pragma GCC target ("tune=native")#pragma GCC target ("avx")#include <iostream>#include <fstream>#include <sstream>#include <iomanip>#include <vector>#include <string>#include <algorithm>#include <queue>#include <stack>#include <map>#include <set>#include <unordered_set>#include <unordered_map>#include <bitset>#include <limits>#include <random>#include <complex>#include <cmath>#include <cstdio>#include <cstdlib>using namespace std;/*******************************************************************/struct Timer {double CYCLE_PER_SEC = 2800000000.0;unsigned long long BEGIN_CYCLE = 0;Timer() {}Timer(double cycle) : CYCLE_PER_SEC(cycle) {}unsigned long long int getCycle() {unsigned int low, high;__asm__ volatile ("rdtsc" : "=a" (low), "=d" (high));return ((unsigned long long int)low) | ((unsigned long long int)high << 32);}void start(void) {BEGIN_CYCLE = getCycle();}double get_time(void) {return (double)(getCycle() - BEGIN_CYCLE) / CYCLE_PER_SEC;}} timer;struct XorShift {unsigned int x;XorShift () : x(2463534242U) {}unsigned int rand() {x ^= (x << 13);x ^= (x >> 17);x ^= (x << 5);return x;}} Random;/*******************************************************************/const double TIME_LIMIT = 0.90;const double TEMP_START = 0.8;const double TEMP_END = 0.001;const double TEMP_DIFF = (TEMP_START - TEMP_END) / TIME_LIMIT;int N,K;int L[500];bool OriA[60][60];bool A[60][60];int CurScore;int BestScore;int Answer[500][4];int BestAnswer[500][4];/*******************************************************************/bool accept (double diff, double temp) {if (diff >= 0) return true;double P = exp(diff / temp) * 4294967295.0;return Random.rand() < P;}int move_rect (int idx, int a2, int b2, int c2, int d2) {int ScoreNxt = CurScore;for (int x = Answer[idx][0]; x <= Answer[idx][2]; x++) {for (int y = Answer[idx][1]; y <= Answer[idx][3]; y++) {if (!A[x][y]) {ScoreNxt--;} else {ScoreNxt++;}A[x][y] = !A[x][y];}}for (int x = a2; x <= c2; x++) {for (int y = b2; y <= d2; y++) {if (!A[x][y]) {ScoreNxt--;} else {ScoreNxt++;}A[x][y] = !A[x][y];}}for (int x = Answer[idx][0]; x <= Answer[idx][2]; x++) {for (int y = Answer[idx][1]; y <= Answer[idx][3]; y++) {A[x][y] = !A[x][y];}}for (int x = a2; x <= c2; x++) {for (int y = b2; y <= d2; y++) {A[x][y] = !A[x][y];}}return ScoreNxt - CurScore;}void simulated_annealing () {int cnt = 0;while (true) {cnt ++;double cur_time = timer.get_time();double cur_temp = TEMP_START - TEMP_DIFF * cur_time;if (cur_time > TIME_LIMIT) break;for (int i = 0; i < K; i++) {int rd = Random.rand() & 1;int lx = rd ? 1 : L[i];int ly = rd ? L[i] : 1;int sx = Random.rand() % (N - lx + 1);int sy = Random.rand() % (N - ly + 1);int diff = move_rect(i, sx, sy, sx + lx - 1, sy + ly - 1);if (accept((double) diff, cur_temp)) {for (int x = Answer[i][0]; x <= Answer[i][2]; x++) {for (int y = Answer[i][1]; y <= Answer[i][3]; y++) {A[x][y] = !A[x][y];}}for (int x = sx; x < sx + lx; x++) {for (int y = sy; y < sy + ly; y++) {A[x][y] = !A[x][y];}}Answer[i][0] = sx;Answer[i][1] = sy;Answer[i][2] = sx + lx - 1;Answer[i][3] = sy + ly - 1;CurScore += diff;if (BestScore < CurScore) {BestScore = CurScore;for (int j = 0; j < K; j++) {for (int k = 0; k < 4; k++) {BestAnswer[j][k] = Answer[j][k];}}}}}}cerr << cnt << endl;}void initialize () {for (int i = 0; i < K; i++) {int rd = Random.rand() & 1;int lx = rd ? 1 : L[i];int ly = rd ? L[i] : 1;int sx = Random.rand() % (N - lx + 1);int sy = Random.rand() % (N - ly + 1);Answer[i][0] = sx;Answer[i][1] = sy;Answer[i][2] = sx + lx - 1;Answer[i][3] = sy + ly - 1;for (int x = sx; x < sx + lx; x++) {for (int y = sy; y < sy + ly; y++) {A[x][y] = !A[x][y];}}}int cnt_ori = 0, cnt_nxt = 0;for (int x = 0; x < N; x++) {for (int y = 0; y < N; y++) {if (!OriA[x][y]) cnt_ori++;if ( !A[x][y]) cnt_nxt++;}}CurScore = cnt_nxt - cnt_ori;BestScore = CurScore;for (int i = 0; i < K; i++) {for (int j = 0; j < 4; j++) {BestAnswer[i][j] = Answer[i][j];}}}int main () {timer.start();cin >> N >> K;for (int i = 0; i < K; i++) {cin >> L[i];}for (int i = 0; i < N; i++) {string line; cin >> line;for (int j = 0; j < N; j++) {if (line[j] == '1') {OriA[i][j] = A[i][j] = true;} else {OriA[i][j] = A[i][j] = false;}}}initialize();simulated_annealing();for (int i = 0; i < K; i++) {for (int j = 0; j < 4; j++) {cout << BestAnswer[i][j] + 1 << (j != 3 ? " " : "\n");}}cerr << BestScore << endl;return 0;}