結果
問題 | No.5002 stick xor |
ユーザー |
![]() |
提出日時 | 2018-05-26 03:51:11 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 27 ms / 1,000 ms |
コード長 | 2,479 bytes |
コンパイル時間 | 2,495 ms |
実行使用メモリ | 1,544 KB |
スコア | 39,729 |
最終ジャッジ日時 | 2018-05-26 03:51:16 |
ジャッジサーバーID (参考情報) |
judge6 / |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 32 |
ソースコード
#include <iostream>#include <vector>#include <string>#include <algorithm>#include <array>#include <cstdio>#include <cstring>#include <cmath>using namespace std;using ll = long long;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;for (int d = 0; d < 2; d++) {for (int i = 0; i < n; i++) {ll a = (1LL << l) - 1;for (int j = 0; j <= n - l; j++) {int c = __builtin_popcountll(b[d][i] & a);if (c > m) {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;}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<pair<int, int>> l(k);for (int h = 0; h < k; h++) {cin >> l[h].first;l[h].second = h;}BB bb(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);}}int s0 = bb.count();sort(l.begin(), l.end());reverse(l.begin(), l.end());vector<array<int, 4>> r(k);int s = 0;for (int h = 0; h < k; h++) {int i, j, d;int l0 = l[h].first;int m = bb.search(l0, i, j, d);auto& a = r[l[h].second];a = { i, j, i, j };a[0]++;a[1]++;a[2 + d] += 1;a[2 + (d ^ 1)] += l0;s += m - (l0 - m);}int s1 = bb.count();if (s != s0 - s1) {cout << s << ' ' << s0 - s1 << endl;throw;}for (int h = 0; h < k; h++) {for (int i = 0; i < 4; i++) {cout << r[h][i] << " \n"[i == 3];}}return 0;}