QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#841994 | #9968. Just Zeros | ucup-team4893# | WA | 11ms | 7736kb | C++17 | 1.7kb | 2025-01-04 09:30:20 | 2025-01-04 09:30:20 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<fstream>
#include<queue>
#include<algorithm>
#define fopen(x, y) freopen(x".in", "r", stdin); freopen(y".out", "w", stdout);
//#define int long long
#ifdef int
#define inf 0x3f3f3f3f3f3f3f3fll
#else
#define inf 0x3f3f3f3f
#endif
using namespace std;
int n, m, q, cnt[256][100005], x[100005], popc[256], cur, sum[256];
int F;
string s;
int calc() {
int res = inf;
for(int i = 0; i < F; i++) {
res = min(res, popc[cur ^ i] + sum[i]);
}
return res;
}
void work() {
cin >> n >> m >> q;
F = (1 << n);
for(int i = 1; i <= n; i++) {
cin >> s;
for(int j = 0; j < s.size(); j++) {
x[j + 1] |= (s[j] & 1) << (i - 1);
}
}
for(int i = 0; i < F; i++) {
for(int j = 1; j <= n; j++) {
cnt[i][j] = popc[x[j] ^ i];
sum[i] += min(cnt[i][j], n - cnt[i][j] + 1);
}
// cout << sum[i] << ' ';
} //cout << '\n';
cout << calc() << '\n';
while(q--) {
char op; cin >> op;
if(op == 'P') {
int k, j; cin >> k >> j;
x[j] ^= 1 << (k - 1);
for(int i = 0; i < F; i++) {
sum[i] -= min(cnt[i][j], n - cnt[i][j] + 1);
cnt[i][j] = popc[x[j] ^ i];
sum[i] += min(cnt[i][j], n - cnt[i][j] + 1);
}
}
else if(op == 'K') {
int j; cin >> j;
x[j] ^= (F - 1);
for(int i = 0; i < F; i++) {
sum[i] -= min(cnt[i][j], n - cnt[i][j] + 1);
cnt[i][j] = popc[x[j] ^ i];
sum[i] += min(cnt[i][j], n - cnt[i][j] + 1);
}
}
else {
int i; cin >> i;
cur ^= 1 << (i - 1);
}
cout << calc() << '\n';
}
}
signed main() {
for(int i = 1; i < 256; i++) {
popc[i] = __builtin_popcount(i);
}
ios::sync_with_stdio(false); cin.tie(0);
int _ = 1;
// cin >> _;
while(_--) work();
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5728kb
input:
3 4 6 1010 1101 0010 R 2 P 3 1 K 2 P 2 1 K 4 P 3 4
output:
3 2 3 4 3 3 4
result:
ok 7 numbers
Test #2:
score: -100
Wrong Answer
time: 11ms
memory: 7736kb
input:
3 4 100000 0100 0011 0011 R 3 K 1 R 2 K 4 R 3 K 2 P 1 1 K 1 R 1 P 1 4 K 4 K 1 K 4 R 3 K 2 K 2 R 1 K 1 K 4 P 3 2 P 2 1 K 1 R 1 P 3 1 R 3 K 3 P 3 2 P 1 3 K 1 R 1 P 1 1 R 1 P 2 1 R 3 P 3 1 R 2 K 2 R 1 R 1 R 3 P 1 3 R 3 K 3 R 2 R 1 P 3 4 K 1 K 1 P 1 4 R 3 K 1 P 1 2 R 1 K 3 P 2 2 R 1 P 1 1 K 4 R 2 P 3 4 ...
output:
3 4 3 2 3 4 3 2 3 3 4 4 3 4 3 4 3 2 3 2 3 4 3 4 4 5 5 5 4 3 4 4 4 5 4 3 4 4 3 4 3 3 4 5 4 4 5 4 5 4 4 4 4 5 5 4 4 3 4 5 4 3 4 4 5 4 5 4 5 4 4 5 5 4 5 5 4 4 4 3 4 3 2 3 4 4 3 4 4 3 3 4 3 4 4 3 4 3 2 3 2 3 2 3 4 3 2 3 4 4 3 4 5 5 5 5 4 4 4 5 4 4 4 5 5 5 4 3 4 3 4 4 5 4 5 5 5 4 3 4 4 5 4 5 4 5 4 3 4 4 ...
result:
wrong answer 1st numbers differ - expected: '4', found: '3'