結果
問題 | No.5002 stick xor |
ユーザー | kosakkun |
提出日時 | 2018-05-26 04:02:16 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 973 ms / 1,000 ms |
コード長 | 7,387 bytes |
コンパイル時間 | 34,587 ms |
実行使用メモリ | 1,620 KB |
スコア | 41,599 |
最終ジャッジ日時 | 2018-05-26 04:02:52 |
ジャッジサーバーID (参考情報) |
judge9 / |
純コード判定しない問題か言語 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 972 ms
1,620 KB |
testcase_01 | AC | 972 ms
1,616 KB |
testcase_02 | AC | 972 ms
1,620 KB |
testcase_03 | AC | 972 ms
1,612 KB |
testcase_04 | AC | 973 ms
1,612 KB |
testcase_05 | AC | 973 ms
1,620 KB |
testcase_06 | AC | 972 ms
1,616 KB |
testcase_07 | AC | 972 ms
1,616 KB |
testcase_08 | AC | 972 ms
1,620 KB |
testcase_09 | AC | 973 ms
1,620 KB |
testcase_10 | AC | 972 ms
1,620 KB |
testcase_11 | AC | 972 ms
1,612 KB |
testcase_12 | AC | 973 ms
1,620 KB |
testcase_13 | AC | 972 ms
1,616 KB |
testcase_14 | AC | 973 ms
1,612 KB |
testcase_15 | AC | 972 ms
1,616 KB |
testcase_16 | AC | 973 ms
1,616 KB |
testcase_17 | AC | 972 ms
1,612 KB |
testcase_18 | AC | 973 ms
1,616 KB |
testcase_19 | AC | 973 ms
1,612 KB |
testcase_20 | AC | 972 ms
1,612 KB |
testcase_21 | AC | 973 ms
1,616 KB |
testcase_22 | AC | 972 ms
1,620 KB |
testcase_23 | AC | 971 ms
1,620 KB |
testcase_24 | AC | 973 ms
1,616 KB |
testcase_25 | AC | 973 ms
1,620 KB |
testcase_26 | AC | 972 ms
1,616 KB |
testcase_27 | AC | 973 ms
1,616 KB |
testcase_28 | AC | 972 ms
1,616 KB |
testcase_29 | AC | 972 ms
1,620 KB |
testcase_30 | AC | 973 ms
1,616 KB |
testcase_31 | AC | 972 ms
1,616 KB |
ソースコード
#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 = 1.00; const double TEMP_END = 0.0001; 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; char Answer[500][4]; char 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 = 0; 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; } 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 sx = -1, sy = -1, ex = -1, ey = -1; int add = (Random.rand() % 2) * (Random.rand() % 2 == 1 ? -1 : 1); if (Random.rand() % 2) { if (Answer[i][0] == Answer[i][2]) { int nxt = add + Answer[i][0]; if (nxt >= N || nxt < 0) continue; sx = nxt; sy = Answer[i][1]; ex = nxt; ey = Answer[i][3]; } else { int snxt = add + Answer[i][0]; int enxt = add + Answer[i][2]; if (snxt >= N || snxt < 0) continue; if (enxt >= N || enxt < 0) continue; sx = snxt; sy = Answer[i][1]; ex = enxt; ey = Answer[i][3]; } } else { if (Answer[i][1] == Answer[i][3]) { int nxt = add + Answer[i][1]; if (nxt >= N || nxt < 0) continue; sx = Answer[i][0]; sy = nxt; ex = Answer[i][2]; ey = nxt; } else { int snxt = add + Answer[i][1]; int enxt = add + Answer[i][3]; if (snxt >= N || snxt < 0) continue; if (enxt >= N || enxt < 0) continue; sx = Answer[i][0]; sy = snxt; ex = Answer[i][2]; ey = enxt; } } int diff = move_rect(i, sx, sy, ex, ey); 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 <= ex; x++) { for (int y = sy; y <= ey; y++) { A[x][y] = !A[x][y]; } } Answer[i][0] = sx; Answer[i][1] = sy; Answer[i][2] = ex; Answer[i][3] = ey; 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; }