QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #831870 | #6309. Aqre | Deltax | AC ✓ | 566ms | 70352kb | C++14 | 2.5kb | 2024-12-25 17:35:07 | 2024-12-25 17:35:07 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void read(T &x) {
x = 0; int f = 1;
char c = getchar();
while (!isdigit(c)) {if (c == '-') f = -f; c = getchar();}
while (isdigit(c)) x = (x << 1) + (x << 3) + (c & 15), c = getchar();
x = x * f;
}
const int MAXN = 1000;
int n, m;
int a[MAXN + 10][MAXN + 10];
int vis[MAXN + 10][MAXN + 10];
inline int cp(int x, int y) {
return 1 <= x && x <= n && 1 <= y && y <= m;
}
void dfs(int x, int y) {
if (vis[x][y]) return;
vis[x][y] = 1;
if (cp(x + 1, y) && a[x + 1][y]) dfs(x + 1, y);
if (cp(x - 1, y) && a[x - 1][y]) dfs(x - 1, y);
if (cp(x, y + 1) && a[x][y + 1]) dfs(x, y + 1);
if (cp(x, y - 1) && a[x][y - 1]) dfs(x, y - 1);
}
bool chk() {
bool fl = 0;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
vis[i][j] = 0;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
if (a[i][j] && !vis[i][j]) {
if (fl) return 0;
fl = 1;
dfs(i, j);
}
return 1;
}
int solve(int *x) {
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
a[i][j] = 1;
for (int i = 1; i <= n; ++i)
for (int j = x[(i - 1) % 4]; j <= m; j += 4)
a[i][j] = 0;
int res = 0;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
res += a[i][j];
if (chk()) return res;
return 0;
}
int main() {
// freopen ("std.in", "r", stdin);
// freopen ("std.out", "w", stdout);
int T; read(T);
while (T--) {
int ans = 0;
read(n); read(m);
int x[4] = {0, 1, 2, 3};
int y[4] = {0, 1, 2, 3};
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
a[i][j] = 1;
if (n <= 3 && m <= 3) {
ans = n * m;
}
else {
if (n == 3 || m == 3) {
if (n == 3) {
for (int i = 4; i <= m; i += 4) {
a[1][i] = 0;
a[3][i] = 0;
}
for (int i = 2; i <= m; i += 4)
a[2][i] = 0;
}
else {
for (int i = 4; i <= n; i += 4) {
a[i][1] = 0;
a[i][3] = 0;
}
for (int i = 2; i <= n; i += 4)
a[i][2] = 0;
}
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
ans += a[i][j];
}
else {
do {
int res = solve(x);
if (res > ans) {
ans = res;
for (int i = 0; i < 4; ++i)
y[i] = x[i];
}
}
while (next_permutation(x, x + 4));
assert(solve(y) == ans);
}
}
printf("%d\n", ans);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j)
printf("%d", a[i][j]);
printf("\n");
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5816kb
input:
3 2 2 3 4 3 8
output:
4 11 11 9 1110 1011 1110 18 11101110 10111011 11101110
result:
ok ok (3 test cases)
Test #2:
score: 0
Accepted
time: 13ms
memory: 6032kb
input:
361 2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9 2 10 2 11 2 12 2 13 2 14 2 15 2 16 2 17 2 18 2 19 2 20 3 2 3 3 3 4 3 5 3 6 3 7 3 8 3 9 3 10 3 11 3 12 3 13 3 14 3 15 3 16 3 17 3 18 3 19 3 20 4 2 4 3 4 4 4 5 4 6 4 7 4 8 4 9 4 10 4 11 4 12 4 13 4 14 4 15 4 16 4 17 4 18 4 19 4 20 5 2 5 3 5 4 5 5 5 6 5 7 5 8 5 9 5 1...
output:
4 11 11 6 111 111 6 1110 0111 8 11101 10111 9 111011 101110 11 1110111 1011101 12 11101110 10111011 14 111011101 101110111 15 1110111011 1011101110 17 11101110111 10111011101 18 111011101110 101110111011 20 1110111011101 1011101110111 21 11101110111011 10111011101110 23 111011101110111 1011101110111...
result:
ok ok (361 test cases)
Test #3:
score: 0
Accepted
time: 237ms
memory: 6856kb
input:
100 91 91 91 92 91 93 91 94 91 95 91 96 91 97 91 98 91 99 91 100 92 91 92 92 92 93 92 94 92 95 92 96 92 97 92 98 92 99 92 100 93 91 93 92 93 93 93 94 93 95 93 96 93 97 93 98 93 99 93 100 94 91 94 92 94 93 94 94 94 95 94 96 94 97 94 98 94 99 94 100 95 91 95 92 95 93 95 94 95 95 95 96 95 97 95 98 95 9...
output:
6211 1110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111 0111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011 1101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110 1011101110111011101...
result:
ok ok (100 test cases)
Test #4:
score: 0
Accepted
time: 286ms
memory: 13652kb
input:
16 247 247 247 248 247 249 247 250 248 247 248 248 248 249 248 250 249 247 249 248 249 249 249 250 250 247 250 248 250 249 250 250
output:
45757 1110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111 0111011101110111011101110111011101110111011101...
result:
ok ok (16 test cases)
Test #5:
score: 0
Accepted
time: 553ms
memory: 69876kb
input:
1 997 997
output:
745507 11101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101...
result:
ok ok (1 test case)
Test #6:
score: 0
Accepted
time: 541ms
memory: 69996kb
input:
1 997 998
output:
746255 11101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101...
result:
ok ok (1 test case)
Test #7:
score: 0
Accepted
time: 535ms
memory: 70108kb
input:
1 997 999
output:
747003 11101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101...
result:
ok ok (1 test case)
Test #8:
score: 0
Accepted
time: 532ms
memory: 70056kb
input:
1 997 1000
output:
747750 11101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101...
result:
ok ok (1 test case)
Test #9:
score: 0
Accepted
time: 524ms
memory: 69992kb
input:
1 998 997
output:
746255 11101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101...
result:
ok ok (1 test case)
Test #10:
score: 0
Accepted
time: 544ms
memory: 70060kb
input:
1 998 998
output:
747004 11101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101...
result:
ok ok (1 test case)
Test #11:
score: 0
Accepted
time: 542ms
memory: 70252kb
input:
1 998 999
output:
747752 11101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101...
result:
ok ok (1 test case)
Test #12:
score: 0
Accepted
time: 559ms
memory: 70256kb
input:
1 998 1000
output:
748500 11101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101...
result:
ok ok (1 test case)
Test #13:
score: 0
Accepted
time: 562ms
memory: 70124kb
input:
1 999 997
output:
747003 11101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101...
result:
ok ok (1 test case)
Test #14:
score: 0
Accepted
time: 560ms
memory: 70112kb
input:
1 999 998
output:
747752 11101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101...
result:
ok ok (1 test case)
Test #15:
score: 0
Accepted
time: 556ms
memory: 70100kb
input:
1 999 999
output:
748501 11101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101...
result:
ok ok (1 test case)
Test #16:
score: 0
Accepted
time: 557ms
memory: 70308kb
input:
1 999 1000
output:
749250 11101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101...
result:
ok ok (1 test case)
Test #17:
score: 0
Accepted
time: 541ms
memory: 70052kb
input:
1 1000 997
output:
747750 11101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101...
result:
ok ok (1 test case)
Test #18:
score: 0
Accepted
time: 566ms
memory: 70232kb
input:
1 1000 998
output:
748500 11101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101...
result:
ok ok (1 test case)
Test #19:
score: 0
Accepted
time: 535ms
memory: 70292kb
input:
1 1000 999
output:
749250 11101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101...
result:
ok ok (1 test case)
Test #20:
score: 0
Accepted
time: 547ms
memory: 70352kb
input:
1 1000 1000
output:
750000 11101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101...
result:
ok ok (1 test case)
Test #21:
score: 0
Accepted
time: 0ms
memory: 5888kb
input:
1 3 997
output:
2244 1110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111...
result:
ok ok (1 test case)
Test #22:
score: 0
Accepted
time: 1ms
memory: 5876kb
input:
1 3 998
output:
2246 1110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111...
result:
ok ok (1 test case)
Test #23:
score: 0
Accepted
time: 1ms
memory: 5936kb
input:
1 3 999
output:
2249 1110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111...
result:
ok ok (1 test case)
Test #24:
score: 0
Accepted
time: 1ms
memory: 7880kb
input:
1 3 1000
output:
2250 1110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111...
result:
ok ok (1 test case)
Test #25:
score: 0
Accepted
time: 0ms
memory: 8808kb
input:
1 997 3
output:
2244 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101...
result:
ok ok (1 test case)
Test #26:
score: 0
Accepted
time: 0ms
memory: 9044kb
input:
1 998 3
output:
2246 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101...
result:
ok ok (1 test case)
Test #27:
score: 0
Accepted
time: 0ms
memory: 9524kb
input:
1 999 3
output:
2249 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101...
result:
ok ok (1 test case)
Test #28:
score: 0
Accepted
time: 0ms
memory: 8828kb
input:
1 1000 3
output:
2250 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101 111 010 111 101...
result:
ok ok (1 test case)
Test #29:
score: 0
Accepted
time: 1ms
memory: 6016kb
input:
1 2 997
output:
1496 1110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111...
result:
ok ok (1 test case)
Test #30:
score: 0
Accepted
time: 0ms
memory: 5956kb
input:
1 2 998
output:
1497 1110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111...
result:
ok ok (1 test case)
Test #31:
score: 0
Accepted
time: 1ms
memory: 5972kb
input:
1 2 999
output:
1499 1110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111...
result:
ok ok (1 test case)
Test #32:
score: 0
Accepted
time: 1ms
memory: 6076kb
input:
1 2 1000
output:
1500 1110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111...
result:
ok ok (1 test case)
Test #33:
score: 0
Accepted
time: 3ms
memory: 11908kb
input:
1 997 2
output:
1496 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 1...
result:
ok ok (1 test case)
Test #34:
score: 0
Accepted
time: 3ms
memory: 11860kb
input:
1 998 2
output:
1497 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 1...
result:
ok ok (1 test case)
Test #35:
score: 0
Accepted
time: 3ms
memory: 11860kb
input:
1 999 2
output:
1499 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 1...
result:
ok ok (1 test case)
Test #36:
score: 0
Accepted
time: 0ms
memory: 11820kb
input:
1 1000 2
output:
1500 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 11 10 11 01 1...
result:
ok ok (1 test case)