結果

問題 No.5002 stick xor
ユーザー merom686merom686
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0