結果
問題 | No.5002 stick xor |
ユーザー | merom686 |
提出日時 | 2018-05-26 13:01:51 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 648 ms / 1,000 ms |
コード長 | 3,430 bytes |
コンパイル時間 | 21,710 ms |
実行使用メモリ | 1,572 KB |
スコア | 43,695 |
最終ジャッジ日時 | 2018-05-26 13:02:35 |
ジャッジサーバーID (参考情報) |
judge10 / |
純コード判定しない問題か言語 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 559 ms
1,572 KB |
testcase_01 | AC | 594 ms
1,568 KB |
testcase_02 | AC | 589 ms
1,572 KB |
testcase_03 | AC | 566 ms
1,568 KB |
testcase_04 | AC | 569 ms
1,568 KB |
testcase_05 | AC | 609 ms
1,568 KB |
testcase_06 | AC | 576 ms
1,568 KB |
testcase_07 | AC | 587 ms
1,572 KB |
testcase_08 | AC | 619 ms
1,568 KB |
testcase_09 | AC | 588 ms
1,572 KB |
testcase_10 | AC | 584 ms
1,572 KB |
testcase_11 | AC | 643 ms
1,568 KB |
testcase_12 | AC | 589 ms
1,572 KB |
testcase_13 | AC | 641 ms
1,568 KB |
testcase_14 | AC | 624 ms
1,572 KB |
testcase_15 | AC | 648 ms
1,568 KB |
testcase_16 | AC | 587 ms
1,568 KB |
testcase_17 | AC | 636 ms
1,568 KB |
testcase_18 | AC | 568 ms
1,572 KB |
testcase_19 | AC | 602 ms
1,568 KB |
testcase_20 | AC | 605 ms
1,568 KB |
testcase_21 | AC | 564 ms
1,572 KB |
testcase_22 | AC | 624 ms
1,568 KB |
testcase_23 | AC | 575 ms
1,572 KB |
testcase_24 | AC | 618 ms
1,572 KB |
testcase_25 | AC | 584 ms
1,572 KB |
testcase_26 | AC | 646 ms
1,568 KB |
testcase_27 | AC | 558 ms
1,568 KB |
testcase_28 | AC | 561 ms
1,568 KB |
testcase_29 | AC | 600 ms
1,572 KB |
testcase_30 | AC | 593 ms
1,568 KB |
testcase_31 | AC | 626 ms
1,572 KB |
ソースコード
#include <iostream> #include <vector> #include <string> #include <algorithm> #include <array> #include <random> #include <cstdio> #include <cstring> #include <cmath> using namespace std; using ll = long long; mt19937_64 rnd; struct BB { BB(int n) : n(n) { for (int d = 0; d < 2; d++) { for (int i = 0; i < n; i++) { b[d][i] = 0; } } } int search(int l, int& i0, int& j0, int& d0) { int m = -1, s = -10000; for (int d = 0; d < 2; d++) { for (int i = 0; i < n; i++) { ll a = (1LL << l) - 1; ll t = (1LL << n) - 1; if (i > 0) t &= b[d][i - 1]; if (i < n - 1) t &= b[d][i + 1]; else t = 0; t ^= b[d][i]; for (int j = 0; j <= n - l; j++) { int c = __builtin_popcountll(b[d][i] & a); int e = c * 64; //if (l > 5) e -= (j > 0 && get(i, j - 1, d)) + (j + l < n && get(i, j + l, d)); e += __builtin_popcountll(t & a); if (e > s) { s = e; m = c; i0 = i; j0 = j; d0 = d; } a <<= 1; } } } for (int h = 0; h < l; h++) { xor1(i0, j0 + h, d0); } if (d0) swap(i0, j0); return m; } void xor1(int i, int j, int d = 0) { b[d][i] ^= 1LL << j; b[d ^ 1][j] ^= 1LL << i; } ll get(int i, int j, int d) { return b[d][i] >> j & 1; } int count() { int s = 0; for (int i = 0; i < n; i++) { s += __builtin_popcountll(b[0][i]); } return s; } int n; ll b[2][60]; }; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, k; cin >> n >> k; vector<array<int, 3>> l(k); for (int h = 0; h < k; h++) { cin >> l[h][1]; //l[h][0] = l[h][1] + rnd() % 70; l[h][2] = h; } BB bb(n), bb0(n); for (int i = 0; i < n; i++) { char a[61]; cin >> a; for (int j = 0; j < n; j++) { if (a[j] == '1') bb.xor1(i, j); } } bb0 = bb; int s2 = 0; vector<array<int, 4>> r(k), r0(k); for (int e = 0; e < 20; e++) { bb = bb0; int s0 = bb.count(); for (int h = 0; h < k; h++) { l[h][0] = l[h][1] + rnd() % (60 + e); } sort(l.begin(), l.end()); reverse(l.begin(), l.end()); int s = 0; for (int h = 0; h < k; h++) { int i, j, d; int l0 = l[h][1]; int m = bb.search(l0, i, j, d); auto& a = r[l[h][2]]; a = { i, j, i, j }; a[0]++; a[1]++; a[2 + d] += 1; a[2 + (d ^ 1)] += l0; s += m - (l0 - m); //cout << m - (l0 - m) << endl; } int s1 = bb.count(); //cout << s << ' ' << s0 << ' ' << s1 << endl; if (s != s0 - s1) { throw; } if (s > s2) { s2 = s; r0 = r; } } for (int h = 0; h < k; h++) { for (int i = 0; i < 4; i++) { cout << r0[h][i] << " \n"[i == 3]; } } return 0; }