QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #706574 | #9465. 基础 01 练习题 | Aaronwrq# | 0 | 15ms | 6028kb | C++14 | 1.3kb | 2024-11-03 12:21:15 | 2024-11-03 12:21:16 |
Judging History
answer
#include <bits/stdc++.h>
#define MAXN 110
using namespace std;
int n, q, op;
bool a[MAXN][MAXN], b[MAXN][MAXN];
int w[1 << 20], dp[1 << 20];
void dfs(const int x, const int y) {
if (x >= n) {
bool flag = 1;
for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) for (int k = 0; k < n; ++k) if (a[i][j] == 1 && b[i][k] == 1 && a[i][k] == 0 && b[i][j] == 0) flag = 0;
for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) for (int k = 0; k < n; ++k) if (a[j][i] == 1 && b[j][i] == 1 && a[k][i] == 0 && b[k][i] == 0) flag = 0;
if (!flag) return;
int now = 0;
for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) if (b[i][j]) now |= 1 << (i * n + j);
w[now] = 1;
return;
}
int newx = x, newy = y + 1;
if (newy >= n) newx = x + 1, newy = 0;
b[x][y] = 0, dfs(newx, newy);
b[x][y] = 1, dfs(newx, newy);
return;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> q >> op;
while (q--) {
int x1, x2, y1, y2;
cin >> x1 >> x2 >> y1 >> y2;
--x1, --x2, --y1, --y2;
for (int i = x1; i <= x2; ++i) for (int j = y1; j <= y2; ++j) a[i][j] ^= 1;
}
dfs(0, 0);
for (int i = 0; i < n * n; ++i) for (int j = (1 << (n * n)) - 1; j >= 0; --j) if (!((j >> i) & 1)) {
dp[j] = max(dp[j], dp[j | (1 << i)] + w[j | (1 << i)]);
}
cout << dp[0] << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 5
Accepted
time: 11ms
memory: 5940kb
input:
4 1000 0 2 3 1 2 1 3 1 3 1 2 1 2 1 2 3 4 1 4 2 4 1 3 1 2 1 4 1 2 1 3 1 4 3 3 2 3 1 2 2 4 4 4 1 3 3 3 3 4 3 4 3 4 2 3 1 1 1 2 2 4 1 4 3 4 3 4 1 2 1 2 2 3 3 4 3 3 1 2 4 4 4 4 2 4 1 4 1 1 1 1 1 3 2 3 2 3 1 1 2 4 2 3 2 4 3 3 1 4 3 3 3 3 1 3 3 3 2 3 2 4 3 3 2 2 1 3 2 4 1 3 1 2 3 4 1 2 2 3 1 3 1 1 1 2 1 2...
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 5
Accepted
time: 15ms
memory: 6028kb
input:
4 1000 0 1 4 3 3 2 3 4 4 3 4 3 4 3 4 1 2 1 4 2 4 2 3 1 3 3 4 2 4 2 3 3 3 3 4 1 3 1 3 1 4 2 3 1 3 1 1 2 2 1 4 3 4 1 4 1 3 1 2 3 4 1 2 1 2 2 3 1 4 2 2 2 2 1 3 1 3 2 2 2 4 1 2 1 4 1 1 1 1 1 2 3 4 4 4 1 3 2 4 1 3 1 1 1 3 1 4 2 2 2 3 1 2 2 2 1 2 1 2 1 4 1 4 2 4 1 2 1 3 1 2 1 3 2 4 2 2 1 2 1 1 1 2 1 3 2 4...
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Wrong Answer
time: 12ms
memory: 5900kb
input:
4 1000 0 1 4 1 2 1 4 2 2 1 4 3 4 2 4 4 4 2 3 3 4 2 4 2 4 1 2 2 2 4 4 2 4 1 3 1 3 1 4 1 4 3 3 3 4 4 4 2 3 2 3 1 4 2 2 1 3 2 3 2 4 2 2 1 4 1 2 2 3 1 4 1 3 4 4 1 4 3 4 1 4 1 2 1 2 1 2 1 3 2 2 3 3 1 2 1 4 1 1 1 4 2 2 1 4 1 4 3 4 2 4 2 4 2 2 1 4 3 4 1 3 2 3 2 4 1 3 1 4 1 3 1 4 3 3 1 3 1 2 1 3 3 3 1 4 1 4...
output:
1
result:
wrong answer 1st numbers differ - expected: '5', found: '1'
Subtask #2:
score: 0
Time Limit Exceeded
Test #4:
score: 0
Time Limit Exceeded
input:
50 200000 0 1 45 2 6 29 44 2 6 31 37 2 50 2 37 1 19 7 13 8 38 38 46 19 38 10 30 30 46 22 42 1 45 5 35 24 27 10 36 19 31 20 47 17 35 7 9 23 42 15 26 31 42 7 8 7 42 1 26 33 48 2 5 30 36 17 44 21 44 5 44 24 36 19 47 15 17 29 36 2 42 31 34 11 41 9 24 12 30 30 43 8 20 2 12 13 20 11 12 10 15 14 22 3 29 2 ...
output:
result:
Subtask #3:
score: 0
Runtime Error
Test #8:
score: 0
Runtime Error
input:
5000 200000 0 1438 2561 3478 4930 1740 4634 87 3003 590 3275 1376 1681 2035 2793 2004 4945 567 3159 550 4470 61 3039 3431 3519 2654 3834 3460 4960 591 3560 409 443 345 2599 746 2891 1288 4570 1577 4402 249 377 1951 4534 2411 2455 294 1192 1679 3153 1645 4259 1735 1856 601 668 477 4881 411 2094 424 1...
output:
result:
Subtask #4:
score: 0
Runtime Error
Test #14:
score: 0
Runtime Error
input:
5000 200000 1 565 4401 1659 1826 429 1640 2999 3495 572 3994 9 3863 3844 4284 2307 3144 1054 1943 358 2592 727 4248 29 1171 1685 2392 4559 4929 1149 2787 1204 1947 2349 2619 405 998 1910 2786 25 1275 912 3475 4384 4387 3822 4895 1849 4548 3082 4749 3457 4220 3174 4885 117 1085 2517 3919 4325 4869 17...
output:
result:
Subtask #5:
score: 0
Runtime Error
Test #21:
score: 0
Runtime Error
input:
200000 200000 1 1 2 1 6 3 4 1 1 5 6 1 5 7 8 1 3 9 10 1 3 11 12 1 6 13 14 1 5 15 16 1 6 17 18 1 6 19 20 1 1 21 22 1 4 23 24 1 5 25 26 1 2 27 28 1 4 29 30 1 3 31 32 1 2 33 34 1 6 35 36 1 3 37 38 1 2 39 40 1 2 41 42 1 3 43 44 1 1 45 46 1 2 47 48 1 3 49 50 1 4 51 52 1 5 53 54 1 1 55 56 1 5 57 58 1 5 59 ...
output:
result:
Subtask #6:
score: 0
Runtime Error
Test #28:
score: 0
Runtime Error
input:
200000 200000 0 91264 123676 6826 154505 121351 188051 108158 131448 65413 163961 26771 116304 93852 110556 34929 187363 31794 142162 33578 38712 26574 67763 178013 197235 46436 146042 95 122860 11683 50463 60177 195245 60862 194711 37817 97212 144366 176271 113551 171098 120095 170517 73555 167299 ...
output:
result:
Subtask #7:
score: 0
Runtime Error
Test #37:
score: 0
Runtime Error
input:
100000 200000 1 1 22878 1 2 1 7957 3 4 1 21779 5 6 1 34321 7 8 1 41692 9 10 1 49473 11 12 1 10254 13 14 1 43995 15 16 1 46975 17 18 1 668 19 20 1 25996 21 22 1 24975 23 24 1 43259 25 26 1 4174 27 28 1 39330 29 30 1 35462 31 32 1 27523 33 34 1 5574 35 36 1 47955 37 38 1 47013 39 40 1 3846 41 42 1 276...