結果
問題 | No.5002 stick xor |
ユーザー | ats5515 |
提出日時 | 2018-06-01 20:50:08 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 959 ms / 1,000 ms |
コード長 | 20,250 bytes |
コンパイル時間 | 33,582 ms |
実行使用メモリ | 2,152 KB |
スコア | 52,451 |
最終ジャッジ日時 | 2018-06-01 20:50:43 |
ジャッジサーバーID (参考情報) |
judge8 / |
純コード判定しない問題か言語 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 956 ms
2,148 KB |
testcase_01 | AC | 957 ms
2,144 KB |
testcase_02 | AC | 957 ms
2,144 KB |
testcase_03 | AC | 957 ms
2,144 KB |
testcase_04 | AC | 957 ms
2,144 KB |
testcase_05 | AC | 957 ms
2,148 KB |
testcase_06 | AC | 957 ms
2,144 KB |
testcase_07 | AC | 956 ms
2,148 KB |
testcase_08 | AC | 957 ms
2,144 KB |
testcase_09 | AC | 957 ms
2,152 KB |
testcase_10 | AC | 957 ms
2,152 KB |
testcase_11 | AC | 957 ms
2,148 KB |
testcase_12 | AC | 958 ms
2,148 KB |
testcase_13 | AC | 957 ms
2,148 KB |
testcase_14 | AC | 957 ms
2,144 KB |
testcase_15 | AC | 959 ms
2,144 KB |
testcase_16 | AC | 958 ms
2,148 KB |
testcase_17 | AC | 957 ms
2,148 KB |
testcase_18 | AC | 957 ms
2,148 KB |
testcase_19 | AC | 957 ms
2,148 KB |
testcase_20 | AC | 957 ms
2,148 KB |
testcase_21 | AC | 956 ms
2,148 KB |
testcase_22 | AC | 957 ms
2,152 KB |
testcase_23 | AC | 957 ms
2,148 KB |
testcase_24 | AC | 957 ms
2,144 KB |
testcase_25 | AC | 957 ms
2,148 KB |
testcase_26 | AC | 955 ms
2,152 KB |
testcase_27 | AC | 957 ms
2,148 KB |
testcase_28 | AC | 957 ms
2,152 KB |
testcase_29 | AC | 958 ms
2,144 KB |
testcase_30 | AC | 956 ms
2,152 KB |
testcase_31 | AC | 957 ms
2,144 KB |
ソースコード
// C++11 #include <algorithm> #include <cmath> #include <iostream> #include <vector> #include <queue> #include <assert.h> #include <fstream> #include <iomanip> using namespace std; const int64_t CYCLES_PER_SEC = 2600000000; const int N = 60; const int K = 500; struct Timer { int64_t start; Timer() { reset(); } void reset() { start = getCycle(); } void plus(double a) { start -= (a * CYCLES_PER_SEC); } inline double get() { return (double)(getCycle() - start) / CYCLES_PER_SEC; } inline int64_t getCycle() { uint32_t low, high; __asm__ volatile ("rdtsc" : "=a" (low), "=d" (high)); return ((int64_t)low) | ((int64_t)high << 32); } }; class XorShift { public: unsigned int x, y, z, w; double nL[65536]; XorShift() { init(); } void init() { x = 314159265; y = 358979323; z = 846264338; w = 327950288; double n = 1 / (double)(2 * 65536); for (int i = 0; i < 65536; i++) { nL[i] = log(((double)i / 65536) + n); } } void seeding(int seed) { x = 314159265; y = 358979323; z = 846264338; w = ((long long)327950288 * (seed + 1)) % 1000000007; for (int i = 0; i < 1000 + (seed % 1000); i++) { next(); } } inline unsigned int next() { unsigned int t = x ^ x << 11; x = y; y = z; z = w; return w = w ^ w >> 19 ^ t ^ t >> 8; } inline double nextLog() { return nL[next() & 0xFFFF]; } inline int nextInt(int m) { return (int)(next() % m); } int nextInt(int min, int max) { return min + nextInt(max - min + 1); } inline double nextDouble() { return (double)next() / ((long long)1 << 32); } }; //The board is rotated by 90 degrees enum Orientation { VERTICAL, HORIZONTAL }; struct Rectangle { int leftX; int topY; Orientation o; }; struct Range { int l, r, u, d; }; typedef char Grid_t; struct State { Rectangle rects[K]; Grid_t grid[N][N]; void init(Grid_t _grid[N][N]) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { grid[i][j] = _grid[i][j]; } } } int calcScore() { int res = N * N; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { res -= grid[i][j]; } } return res; } int doPlace(int i, int L) { int res = 0; if (rects[i].o == VERTICAL) { int x = rects[i].leftX; for (int y = rects[i].topY; y < rects[i].topY + L; y++) { res += grid[x][y]; grid[x][y] = 1 - grid[x][y]; } } else { int y = rects[i].topY; for (int x = rects[i].leftX; x < rects[i].leftX + L; x++) { res += grid[x][y]; grid[x][y] = 1 - grid[x][y]; } } return res * 2 - L; } int erase(int i, int L) { int res = 0; if (rects[i].o == VERTICAL) { int x = rects[i].leftX; for (int y = rects[i].topY; y < rects[i].topY + L; y++) { res += grid[x][y]; grid[x][y] = 1 - grid[x][y]; } } else { int y = rects[i].topY; for (int x = rects[i].leftX; x < rects[i].leftX + L; x++) { res += grid[x][y]; grid[x][y] = 1 - grid[x][y]; } } return res * 2 - L; } int placeGreedy(int i, int L, XorShift &rnd, Range &ra) { int ones; int mx = -1; int l; int sc; //if (rects[i].o == VERTICAL) { for (int x = ra.l; x < ra.r; x++) { ones = 0; for (int y = ra.u; y < ra.u + L; y++) { ones += grid[x][y]; } l = ra.u; while (true) { sc = (ones << 12) + (rnd.next() & 0xFFF); if (mx < sc) { mx = sc; rects[i].leftX = x; rects[i].topY = l; rects[i].o = VERTICAL; } if (l + L >= ra.d)break; ones += grid[x][l + L]; ones -= grid[x][l]; l++; } } /* } else {*/ for (int y = ra.u; y < ra.d; y++) { ones = 0; for (int x = ra.l; x < ra.l + L; x++) { ones += grid[x][y]; } l = ra.l; while (true) { sc = (ones << 12) + (rnd.next() & 0xFFF); if (mx < sc) { mx = sc; rects[i].leftX = l; rects[i].topY = y; rects[i].o = HORIZONTAL; } if (l + L >= ra.r)break; ones += grid[l + L][y]; ones -= grid[l][y]; l++; } } //} return doPlace(i, L); } int placeGreedy(int i, int L, XorShift &rnd) { int ones; int mx = -1; int rr = -1; int l; int sc; //if (rects[i].o == VERTICAL) { for (int x = 0; x < N; x++) { ones = 0; for (int y = 0; y < L; y++) { ones += grid[x][y]; } l = 0; while (true) { if (rr <= ones) { sc = (ones << 12) + (rnd.next() & 0xFFF); if (mx < sc) { rr = ones; mx = sc; rects[i].leftX = x; rects[i].topY = l; rects[i].o = VERTICAL; } } if (l + L >= N)break; ones += grid[x][l + L]; ones -= grid[x][l]; l++; } } /* } else {*/ for (int y = 0; y < N; y++) { ones = 0; for (int x = 0; x < L; x++) { ones += grid[x][y]; } l = 0; while (true) { if (rr <= ones) { sc = (ones << 12) + (rnd.next() & 0xFFF); if (mx < sc) { mx = sc; rr = ones; rects[i].leftX = l; rects[i].topY = y; rects[i].o = HORIZONTAL; } } if (l + L >= N)break; ones += grid[l + L][y]; ones -= grid[l][y]; l++; } } //} return doPlace(i, L); } int placeGreedyH(int i, int L, XorShift &rnd) { int ones; int mx = -1; int l; int sc; //if (rects[i].o == VERTICAL) { for (int x = 0; x < N; x++) { ones = 0; for (int y = 0; y < L; y++) { ones += grid[x][y]; } l = 0; while (true) { sc = (ones << 12) + (rnd.next() & 0xFFF); if (mx < sc) { mx = sc; rects[i].leftX = x; rects[i].topY = l; rects[i].o = VERTICAL; } if (l + L >= N)break; ones += grid[x][l + L]; ones -= grid[x][l]; l++; } } /* } else {*/ /* for (int y = 0; y < N; y++) { ones = 0; for (int x = 0; x < L; x++) { ones += grid[x][y]; } l = 0; while (true) { sc = (ones << 12) + (rnd.next() & 0xFFF); if (mx < sc) { mx = sc; rects[i].leftX = l; rects[i].topY = y; rects[i].o = HORIZONTAL; } if (l + L >= N)break; ones += grid[l + L][y]; ones -= grid[l][y]; l++; } }*/ //} return doPlace(i, L); } int placeGreedyRange(int i, int L, XorShift &rnd, double range) { int ones; double mx = -1; int l; double sc; int res; for (int x = 0; x < N; x++) { ones = 0; for (int y = 0; y < L; y++) { ones += grid[x][y]; } l = 0; while (true) { sc = ones + range * rnd.nextDouble(); if (mx < sc) { mx = sc; res = ones; rects[i].leftX = x; rects[i].topY = l; rects[i].o = VERTICAL; } if (l + L >= N)break; ones += grid[x][l + L]; ones -= grid[x][l]; l++; } } for (int y = 0; y < N; y++) { ones = 0; for (int x = 0; x < L; x++) { ones += grid[x][y]; } l = 0; while (true) { sc = ones + range * rnd.nextDouble(); if (mx < sc) { mx = sc; res = ones; rects[i].leftX = l; rects[i].topY = y; rects[i].o = HORIZONTAL; } if (l + L >= N)break; ones += grid[l + L][y]; ones -= grid[l][y]; l++; } } doPlace(i, L); return res * 2 - L; } }; class Solver { public: XorShift rnd; Timer timer; //////TASK/////// Grid_t grid[N][N]; int L[K]; int L_sorted[K]; int h[27]; int W0; ///////////////// State state; void inputFromStdin() { int _; cin >> _ >> _; for (int i = 0; i < K; i++) { cin >> L[i]; } W0 = N * N; char a; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { cin >> a; grid[i][j] = a - '0'; W0 -= grid[i][j]; } } } void generateTestCase(int seed) { XorShift gen; gen.seeding(seed); for (int i = 0; i < K; i++) { L[i] = gen.nextInt(25) + 1; } sort(L, L + K, greater<int>()); W0 = N * N; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { grid[i][j] = gen.nextInt(2); W0 -= grid[i][j]; } } ofstream ofs("input.txt"); ofs << N << " " << K << endl; for (int i = 0; i < K; i++) { if (i > 0)ofs << " "; ofs << L[i]; } ofs << endl; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { ofs << (int)grid[i][j]; } ofs << endl; } } void outputResult() { int head[25]; for (int i = 0; i < K; i++) { if (i == 0 || L_sorted[i] > L_sorted[i - 1]) { head[L_sorted[i] - 1] = i; } } for (int i = 0; i < K; i++) { Rectangle &r = state.rects[head[L[i] - 1]]; if (r.o == VERTICAL) { cout << r.leftX + 1 << " " << r.topY + 1 << " " << r.leftX + 1 << " " << r.topY + L[i] << endl; } else { cout << r.leftX + 1 << " " << r.topY + 1 << " " << r.leftX + L[i] << " " << r.topY + 1 << endl; } head[L[i] - 1]++; } } void outputDebugInfo() { int W1 = state.calcScore(); cerr << "W0 = " << W0 << ", W1 = " << W1 << endl; cerr << "score = " << W1 - W0 << endl; } int getScore() { int W1 = state.calcScore(); return W1 - W0; } void init() { state.init(grid); for (int i = 0; i < K; i++) { L_sorted[i] = L[i]; } sort(L_sorted, L_sorted + K); h[0] = 0; for (int i = 0; i < K; i++) { if (i == 0 || L_sorted[i] > L_sorted[i - 1]) { h[L_sorted[i]] = i; } } h[26] = K; } void SA(double timelimit) { int score = state.calcScore(); /*for (int i = K - 1; i >= 0; i--) { score += state.placeGreedy(i, L_sorted[i], rnd); }*/ /*for (int i = 0; i < K; i++) { score += state.placeGreedy(i, L_sorted[i], rnd); }*/ double ti; int a; int o; int cnt = 0; cerr << score << endl; cerr << state.calcScore() << endl; a = K - 1; double st = timer.get(); cerr << "st=" << st << endl; double di = st; double dd = (timelimit - st) * 0.1; double rem; Rectangle tmp; double T; double T0 = 1.1; int bscore; int br = 500; int rr; int mnL = K; int xa; int ya; int xb; int yb; int la; int b; int lb; Rectangle ba, bb; while (true) { if ((cnt & 0x3FF) == 0) { ti = timer.get(); if (ti > timelimit) { break; } rem = (timelimit - ti) / (timelimit - st); if (rem > 0) { rr = 350 * rem; if (rr < br) { for (int i = br - 1; i >= rr; i--) { score += state.placeGreedy(i, L_sorted[i], rnd); } br = rr; mnL = min(mnL, rr); } } T = T0 * rem; if (di < ti) { di += dd; cerr << score << " " << rr << endl; } } cnt++; bscore = score; if (rnd.nextDouble() < 0.002) { a = rnd.nextInt(rr, K - 1); score += state.erase(a, L_sorted[a]); score += state.placeGreedy(a, L_sorted[a], rnd); /*tmp = state.rects[a]; o = rnd.nextInt(2); if (o == 0) { state.rects[a].o = VERTICAL; state.rects[a].leftX = rnd.nextInt(N); state.rects[a].topY = rnd.nextInt(N + 1 - L_sorted[a]); } else { state.rects[a].o = HORIZONTAL; state.rects[a].leftX = rnd.nextInt(N + 1 - L_sorted[a]); state.rects[a].topY = rnd.nextInt(N); } score += state.doPlace(a, L_sorted[a]); if (score - bscore > T*rnd.nextLog()) { } else { score += state.erase(a, L_sorted[a]); state.rects[a] = tmp; score += state.doPlace(a, L_sorted[a]); }*/ } else { a = rnd.nextInt(rr, h[25] - 1); la = L_sorted[a]; ba = state.rects[a]; if (state.rects[a].o == VERTICAL) { if (rnd.nextInt(2)) { if (state.rects[a].topY > 0) { score += 2 * state.grid[state.rects[a].leftX][state.rects[a].topY - 1] - 1; state.rects[a].topY--; xa = state.rects[a].leftX; ya = state.rects[a].topY; state.grid[xa][ya] ^= 1; } else { continue; } } else { if (state.rects[a].topY + la < N) { score += 2 * state.grid[state.rects[a].leftX][state.rects[a].topY + la] - 1; xa = state.rects[a].leftX; ya = state.rects[a].topY + la; state.grid[xa][ya] ^= 1; } else { continue; } } } else { if (rnd.nextInt(2)) { if (state.rects[a].leftX > 0) { score += 2 * state.grid[state.rects[a].leftX - 1][state.rects[a].topY] - 1; state.rects[a].leftX--; xa = state.rects[a].leftX; ya = state.rects[a].topY; state.grid[xa][ya] ^= 1; } else { continue; } } else { if (state.rects[a].leftX + la < N) { score += 2 * state.grid[state.rects[a].leftX + la][state.rects[a].topY] - 1; xa = state.rects[a].leftX + la; ya = state.rects[a].topY; state.grid[xa][ya] ^= 1; } else { continue; } } } b = rnd.nextInt(h[la + 1], h[la + 2] - 1); bb = state.rects[b]; lb = L_sorted[b]; if (lb != la + 1)assert(false); if (state.rects[b].o == VERTICAL) { if (rnd.nextInt(2)) { score += 2 * state.grid[state.rects[b].leftX][state.rects[b].topY] - 1; xb = state.rects[b].leftX; yb = state.rects[b].topY; state.rects[b].topY++; } else { score += 2 * state.grid[state.rects[b].leftX][state.rects[b].topY + lb - 1] - 1; xb = state.rects[b].leftX; yb = state.rects[b].topY + lb - 1; } } else { if (rnd.nextInt(2)) { score += 2 * state.grid[state.rects[b].leftX][state.rects[b].topY] - 1; xb = state.rects[b].leftX; yb = state.rects[b].topY; state.rects[b].leftX++; } else { score += 2 * state.grid[state.rects[b].leftX + lb - 1][state.rects[b].topY] - 1; xb = state.rects[b].leftX + lb - 1; yb = state.rects[b].topY; } } if (score - bscore > T*rnd.nextLog()) { swap(state.rects[a], state.rects[b]); state.grid[xb][yb] ^= 1; //cerr << "ok" << endl; } else { score = bscore; state.rects[a] = ba; state.rects[b] = bb; state.grid[xa][ya] ^= 1; } } } cerr << score << endl; cerr << "cnt = " << cnt << endl; } void greedy(double timelimit) { int score = state.calcScore(); /* for (int i = K - 1; i >= 0; i--) { score += state.placeGreedy(i, L_sorted[i], rnd); }*/ /*for (int i = 0; i < K; i++) { score += state.placeGreedy(i, L_sorted[i], rnd); }*/ for (int i = 0; i < K; i++) { if (i % 2 == 0) { state.rects[i].o = VERTICAL; } else { state.rects[i].o = HORIZONTAL; } } double ti; int a; int cnt = 0; cerr << score << endl; cerr << state.calcScore() << endl; a = K - 1; double st = timer.get(); double di = st; cerr << "st=" << st << endl; double dd = (timelimit - st)*0.1; double rem; int br = 500; int rr; int mnL = K; double m = 1.0 * timelimit; while (true) { ti = timer.get(); if (ti > timelimit) { break; } rem = (m - ti) / (m - st); if (rem > 0) { rr = 450 * pow(rem, 3); if (rr < br) { for (int i = br - 1; i >= rr; i--) { score += state.placeGreedy(i, L_sorted[i], rnd); } br = rr; mnL = min(mnL, L_sorted[rr]); } } if (di < ti) { di += dd; cerr << score << " " << rr << endl; } cnt++; //if (rnd.nextDouble() < 0.5) { a = rnd.nextInt(rr, K - 1); //a = rnd.nextInt(rr, rr + 150); //if ((--a) == -1)a = -1; score += state.erase(a, L_sorted[a]); score += state.placeGreedy(a, L_sorted[a], rnd); /*} else { if (cnt & 1) { } else { } }*/ } cerr << score << endl; cerr << "cnt = " << cnt << endl; } void greedy2(double timelimit) { vector<Range> ra(K); { /*int xx = 4; for (int i = 0; i < K; i++) { int ii = i % (xx*xx); int ll = L_sorted[i] + 15; ra[i].l = (ii % xx) * (N - ll) / (xx - 1); ra[i].u = (ii / xx) * (N - ll) / (xx - 1); ra[i].r = ra[i].l + ll; ra[i].d = ra[i].u + ll; }*/ int xx = 4; for (int i = 0; i < K; i++) { int ii = i % (xx*xx); int ll = max(18, 2 * L_sorted[i] + 10); ra[i].l = (ii % xx) * (N - ll) / (xx - 1); ra[i].u = (ii / xx) * (N - ll) / (xx - 1); ra[i].r = ra[i].l + ll; ra[i].d = ra[i].u + ll; } /*for (int i = 0; i < K; i++) { ra[i].l = 0; ra[i].u = 0; ra[i].r = ra[i].l + 45; ra[i].d = ra[i].u + 45; }*/ } int score = state.calcScore(); /* for (int i = K - 1; i >= 0; i--) { score += state.placeGreedy(i, L_sorted[i], rnd); }*/ /*for (int i = 0; i < K; i++) { score += state.placeGreedy(i, L_sorted[i], rnd); }*/ for (int i = 0; i < K; i++) { if (i % 2 == 0) { state.rects[i].o = VERTICAL; } else { state.rects[i].o = HORIZONTAL; } } double ti; int a; int cnt = 0; cerr << score << endl; cerr << state.calcScore() << endl; double di; a = K - 1; double st = timer.get(); cerr << "st=" << st << endl; double dd = (timelimit - st)*0.1; double rem; int br = 500; int rr; while (true) { ti = timer.get(); if (ti > timelimit) { break; } rem = (timelimit - ti) / (timelimit - st); rr = 350 * rem; if (rr < br) { for (int i = rr; i < br; i++) { score += state.placeGreedy(i, L_sorted[i], rnd, ra[i]); } br = rr; } if (di < ti) { di += dd; cerr << score << endl; } cnt++; a = rnd.nextInt(rr, K - 1); //if ((--a) == -1)a = -1; score += state.erase(a, L_sorted[a]); score += state.placeGreedy(a, L_sorted[a], rnd, ra[a]); //if (state.rects[a].o == VERTICAL) { // if (state.rects[a].topY < 30 && state.rects[a].topY + L_sorted[a] - 1 >= 30) { // cerr << state.rects[a].leftX << " " << state.rects[a].topY << " " << L_sorted[a] << endl; // //assert(false); // } //} //else if (state.rects[a].o == HORIZONTAL) { // if (state.rects[a].leftX < 30 && state.rects[a].leftX + L_sorted[a] - 1 >= 30) { // cerr << state.rects[a].leftX << " " << state.rects[a].topY << " " << L_sorted[a] << endl; // // assert(false); // } //} } cerr << score << endl; cerr << "cnt = " << cnt << endl; } void greedy3(double timelimit) { int score = state.calcScore(); double ti; int a; int cnt = 0; cerr << score << endl; cerr << state.calcScore() << endl; a = K - 1; double st = timer.get(); double di = st; cerr << "st=" << st << endl; double dd = (timelimit - st)*0.1; double rem; int br = 500; int rr; double m = 1.0 * timelimit; while (true) { ti = timer.get(); if (ti > timelimit) { break; } if (di < ti) { di += dd; cerr << score << " " << rr << endl; } cnt++; a = rnd.nextInt(K); //a = rnd.nextInt(rr, rr + 150); //if ((--a) == -1)a = -1; score += state.erase(a, L_sorted[a]); score += state.placeGreedy(a, L_sorted[a], rnd); } cerr << score << endl; cerr << "cnt = " << cnt << endl; } void greedy4(double timelimit) { int score = state.calcScore(); /* for (int i = K - 1; i >= 0; i--) { score += state.placeGreedy(i, L_sorted[i], rnd); }*/ /*for (int i = 0; i < K; i++) { score += state.placeGreedy(i, L_sorted[i], rnd); }*/ double ti; int a; int cnt = 0; cerr << score << endl; cerr << state.calcScore() << endl; a = K - 1; double st = timer.get(); double di = st; cerr << "st=" << st << endl; double dd = (timelimit - st)*0.1; double rem; int br = 500; int rr; double m = 1.0 * timelimit; while (true) { ti = timer.get(); if (ti > timelimit) { break; } rem = (m - ti) / (m - st); if (rem > 0) { rr = 350 * rem; if (rr < br) { for (int i = br - 1; i >= rr; i--) { score += state.placeGreedyH(i, L_sorted[i], rnd); } br = rr; } } if (di < ti) { di += dd; cerr << score << " " << rr << endl; } cnt++; a = rnd.nextInt(rr, K - 1); //a = rnd.nextInt(rr, rr + 150); //if ((--a) == -1)a = -1; score += state.erase(a, L_sorted[a]); score += state.placeGreedyH(a, L_sorted[a], rnd); } cerr << score << endl; cerr << "cnt = " << cnt << endl; } void solve() { init(); //greedy(0.1); //greedy2(0.95); SA(0.95); //greedy4(10); //greedy3(0.95); outputDebugInfo(); } }; //#define Batch #ifdef Batch int main() { ofstream ofs("result.csv"); for (int seed = 0; seed < 30; seed++) { Solver solver; solver.generateTestCase(seed); solver.solve(); ofs << seed << "," << solver.getScore() << endl; } } #else int main() { Solver solver; //solver.generateTestCase(10); solver.inputFromStdin(); solver.solve(); solver.outputResult(); } #endif // Batch