QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #674051 | #6309. Aqre | ji_114514# | AC ✓ | 381ms | 27776kb | C++20 | 3.9kb | 2024-10-25 13:26:49 | 2024-10-25 13:26:50 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e3 + 10;
int n, m, ans[N][N], te[N][N];
int p[] = {0, 3, 2, 4, 1};
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
bool vis[N][N];
bool check()
{
int cnt = 0, u = 0, xt, yt;
queue<int>q;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++) {
cnt -= te[i][j];
if (j >= 4)
{
int t[2] = {0};
for (int k = 0; k < 4; k++)t[te[i][j - k]]++;
if (!t[0] || !t[1])return 0;
}
if (i >= 4)
{
int t[2] = {0};
for (int k = 0; k < 4; k++)t[te[i - k][j]]++;
if (!t[0] || !t[1])return 0;
}
vis[i][j] = 0;
if (te[i][j])u = (i - 1) * m + j, xt = i, yt = j;
}
}
if (u)q.push(u), vis[xt][yt] = 1;
while (!q.empty())
{
int u = q.front(); q.pop();
cnt++;
int x = (u - 1) / m + 1, y = (u - 1) % m + 1;
for (int k = 0; k < 4; k++)
{
int nx = x + dx[k], ny = y + dy[k];
if (nx == 0 || ny == 0 || nx > n || ny > m || vis[nx][ny] || te[nx][ny] == 0)continue;
int v = (nx - 1) * m + ny;
vis[nx][ny] = 1;
q.push(v);
}
}
return cnt == 0;
}
void solve()
{
cin >> n >> m;
int res = 0;
for (int st = 0; st < 256; st++)
{
int temp = st;
for (int i = 1; i <= 4; i++)
{
p[i] = temp % 4 + 1;
temp /= 4;
}
int s = ((n + 3) / 4) * 4, t = ((m + 3) / 4) * 4;
for (int i = 1; i <= s / 4; i++)
{
for (int k = 1; k <= 4; k++)
{
for (int j = 1; j <= t / 4; j++)
{
for (int q = 1; q <= 4; q++)
{
int x = (i - 1) * 4 + k, y = (j - 1) * 4 + q;
if (p[k] == q)te[x][y] = 0;
else te[x][y] = 1;
}
}
}
}
int cnt = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
cnt += te[i][j];
}
if (cnt > res && check() ) {
res = cnt;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)ans[i][j] = te[i][j];
}
}
swap(n, m);
for (int st = 0; st < 256; st++)
{
int temp = st;
for (int i = 1; i <= 4; i++)
{
p[i] = temp % 4 + 1;
temp /= 4;
}
int s = ((n + 3) / 4) * 4, t = ((m + 3) / 4) * 4;
for (int i = 1; i <= s / 4; i++)
{
for (int k = 1; k <= 4; k++)
{
for (int j = 1; j <= t / 4; j++)
{
for (int q = 1; q <= 4; q++)
{
int x = (i - 1) * 4 + k, y = (j - 1) * 4 + q;
if (p[k] == q)te[x][y] = 0;
else te[x][y] = 1;
}
}
}
}
int cnt = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
cnt += te[i][j];
}
if (cnt > res && check() ) {
res = cnt;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)ans[j][i] = te[i][j];
}
}
swap(n, m);
cout << res << '\n';
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)cout << ans[i][j];
cout << '\n';
}
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--)solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7648kb
input:
3 2 2 3 4 3 8
output:
4 11 11 9 0111 0111 0111 18 11011101 01110111 01110111
result:
ok ok (3 test cases)
Test #2:
score: 0
Accepted
time: 24ms
memory: 7772kb
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 0111 0111 8 11101 10111 9 110111 011101 11 1110111 1011101 12 11011101 01110111 14 111011101 101110111 15 1101110111 0111011101 17 11101110111 10111011101 18 110111011101 011101110111 20 1110111011101 1011101110111 21 11011101110111 01110111011101 23 111011101110111 1011101110111...
result:
ok ok (361 test cases)
Test #3:
score: 0
Accepted
time: 280ms
memory: 11812kb
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 1101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110 1110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111 1011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101 0111011101110111011...
result:
ok ok (100 test cases)
Test #4:
score: 0
Accepted
time: 343ms
memory: 12464kb
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 1101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110 1110111011101110111011101110111011101110111011...
result:
ok ok (16 test cases)
Test #5:
score: 0
Accepted
time: 370ms
memory: 25768kb
input:
1 997 997
output:
745507 11011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011...
result:
ok ok (1 test case)
Test #6:
score: 0
Accepted
time: 363ms
memory: 26348kb
input:
1 997 998
output:
746255 11011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011...
result:
ok ok (1 test case)
Test #7:
score: 0
Accepted
time: 378ms
memory: 27716kb
input:
1 997 999
output:
747003 11101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101...
result:
ok ok (1 test case)
Test #8:
score: 0
Accepted
time: 381ms
memory: 25248kb
input:
1 997 1000
output:
747750 11101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101...
result:
ok ok (1 test case)
Test #9:
score: 0
Accepted
time: 362ms
memory: 26476kb
input:
1 998 997
output:
746255 11011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011...
result:
ok ok (1 test case)
Test #10:
score: 0
Accepted
time: 364ms
memory: 26144kb
input:
1 998 998
output:
747004 11011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011...
result:
ok ok (1 test case)
Test #11:
score: 0
Accepted
time: 365ms
memory: 25212kb
input:
1 998 999
output:
747752 11011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011...
result:
ok ok (1 test case)
Test #12:
score: 0
Accepted
time: 375ms
memory: 26252kb
input:
1 998 1000
output:
748500 11101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101...
result:
ok ok (1 test case)
Test #13:
score: 0
Accepted
time: 366ms
memory: 25768kb
input:
1 999 997
output:
747003 11011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011...
result:
ok ok (1 test case)
Test #14:
score: 0
Accepted
time: 366ms
memory: 25980kb
input:
1 999 998
output:
747752 11011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011...
result:
ok ok (1 test case)
Test #15:
score: 0
Accepted
time: 365ms
memory: 25272kb
input:
1 999 999
output:
748501 11011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011...
result:
ok ok (1 test case)
Test #16:
score: 0
Accepted
time: 375ms
memory: 27776kb
input:
1 999 1000
output:
749250 11101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101...
result:
ok ok (1 test case)
Test #17:
score: 0
Accepted
time: 361ms
memory: 24980kb
input:
1 1000 997
output:
747750 11011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011...
result:
ok ok (1 test case)
Test #18:
score: 0
Accepted
time: 371ms
memory: 27628kb
input:
1 1000 998
output:
748500 11101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101...
result:
ok ok (1 test case)
Test #19:
score: 0
Accepted
time: 371ms
memory: 25268kb
input:
1 1000 999
output:
749250 11011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011...
result:
ok ok (1 test case)
Test #20:
score: 0
Accepted
time: 374ms
memory: 25184kb
input:
1 1000 1000
output:
750000 11101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101...
result:
ok ok (1 test case)
Test #21:
score: 0
Accepted
time: 0ms
memory: 15780kb
input:
1 3 997
output:
2244 1110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111...
result:
ok ok (1 test case)
Test #22:
score: 0
Accepted
time: 0ms
memory: 15892kb
input:
1 3 998
output:
2246 1101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110...
result:
ok ok (1 test case)
Test #23:
score: 0
Accepted
time: 0ms
memory: 15868kb
input:
1 3 999
output:
2249 1110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111...
result:
ok ok (1 test case)
Test #24:
score: 0
Accepted
time: 0ms
memory: 15828kb
input:
1 3 1000
output:
2250 1101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110...
result:
ok ok (1 test case)
Test #25:
score: 0
Accepted
time: 0ms
memory: 27584kb
input:
1 997 3
output:
2244 111 101 110 011 111 101 110 011 111 101 110 011 111 101 110 011 111 101 110 011 111 101 110 011 111 101 110 011 111 101 110 011 111 101 110 011 111 101 110 011 111 101 110 011 111 101 110 011 111 101 110 011 111 101 110 011 111 101 110 011 111 101 110 011 111 101 110 011 111 101 110 011 111 101...
result:
ok ok (1 test case)
Test #26:
score: 0
Accepted
time: 6ms
memory: 25128kb
input:
1 998 3
output:
2246 110 111 101 011 110 111 101 011 110 111 101 011 110 111 101 011 110 111 101 011 110 111 101 011 110 111 101 011 110 111 101 011 110 111 101 011 110 111 101 011 110 111 101 011 110 111 101 011 110 111 101 011 110 111 101 011 110 111 101 011 110 111 101 011 110 111 101 011 110 111 101 011 110 111...
result:
ok ok (1 test case)
Test #27:
score: 0
Accepted
time: 0ms
memory: 24960kb
input:
1 999 3
output:
2249 111 110 111 001 111 110 111 001 111 110 111 001 111 110 111 001 111 110 111 001 111 110 111 001 111 110 111 001 111 110 111 001 111 110 111 001 111 110 111 001 111 110 111 001 111 110 111 001 111 110 111 001 111 110 111 001 111 110 111 001 111 110 111 001 111 110 111 001 111 110 111 001 111 110...
result:
ok ok (1 test case)
Test #28:
score: 0
Accepted
time: 0ms
memory: 26436kb
input:
1 1000 3
output:
2250 110 111 101 011 110 111 101 011 110 111 101 011 110 111 101 011 110 111 101 011 110 111 101 011 110 111 101 011 110 111 101 011 110 111 101 011 110 111 101 011 110 111 101 011 110 111 101 011 110 111 101 011 110 111 101 011 110 111 101 011 110 111 101 011 110 111 101 011 110 111 101 011 110 111...
result:
ok ok (1 test case)
Test #29:
score: 0
Accepted
time: 0ms
memory: 13788kb
input:
1 2 997
output:
1496 1110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111...
result:
ok ok (1 test case)
Test #30:
score: 0
Accepted
time: 0ms
memory: 18904kb
input:
1 2 998
output:
1497 1101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110...
result:
ok ok (1 test case)
Test #31:
score: 0
Accepted
time: 0ms
memory: 15928kb
input:
1 2 999
output:
1499 1110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111...
result:
ok ok (1 test case)
Test #32:
score: 0
Accepted
time: 3ms
memory: 16076kb
input:
1 2 1000
output:
1500 1101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110111011101110...
result:
ok ok (1 test case)
Test #33:
score: 0
Accepted
time: 0ms
memory: 25788kb
input:
1 997 2
output:
1496 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 11 10 1...
result:
ok ok (1 test case)
Test #34:
score: 0
Accepted
time: 0ms
memory: 25892kb
input:
1 998 2
output:
1497 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 11 10 1...
result:
ok ok (1 test case)
Test #35:
score: 0
Accepted
time: 0ms
memory: 27208kb
input:
1 999 2
output:
1499 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 11 10 1...
result:
ok ok (1 test case)
Test #36:
score: 0
Accepted
time: 2ms
memory: 25712kb
input:
1 1000 2
output:
1500 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 11 10 1...
result:
ok ok (1 test case)