QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#101563 | #6377. LaLa and Magic Stone | zhoukangyang# | WA | 3ms | 7376kb | C++17 | 3.1kb | 2023-04-30 11:18:47 | 2023-04-30 11:18:49 |
Judging History
answer
#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long
#define vi vector <int>
#define sz(a) ((int) (a).size())
#define me(f, x) memset(f, x, sizeof(f))
#define uint unsigned int
#define ull unsigned long long
#define bs bitset < N >
using namespace std;
const int N = 2007, mod = 998244353;
int n, m;
char s[N][N], S[N][N];
int gen[N], tp;
inline bool canput(int x, int y) {
if(s[x][y] == '1' || s[x][y + 2] == '1' || s[x + 2][y] == '1' || s[x + 2][y + 2] == '1')
return 0;
if((s[x + 1][y] - '0') + (s[x][y + 1] - '0') +
(s[x + 1][y + 2] - '0') + (s[x + 2][y + 1] - '0') > 1) return 0;
return 1;
}
vector < pair < int, int > > rt[N];
int main() {
// freopen("data.in", "r", stdin);
ios :: sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> m;
L(i, 1, n) {
cin >> (s[i] + 1);
}
L(i, 1, n) {
L(j, 1, m) {
S[i][j] = s[i][j];
}
}
auto put = [&] (int x, int y) {
if(x < 1 || x > n || y < 1 || y > m || s[x][y] == '1') {
// cout<<x <<' '<<y<<endl;
// cout << "0" << endl;
exit(0);
}
s[x][y] = '1';
return ;
};
int ans = 1;
L(sum, 2, n + m) {
for(auto u : rt[sum]) {
int x1 = u.first, y1 = sum - x1;
int x2 = u.second, y2 = sum - x2;
if(s[x1][y1] == '1') {
put(x2, y2);
} else if(s[x2][y2] == '1') {
put(x1, y1);
} else if(canput(x1, y1)) {
put(x2, y2);
} else {
put(x1, y1);
}
}
tp = 0;
L(i, 1, n) {
int j = sum - i;
if(1 <= j && j <= m && s[i][j] == '0') {
// cout << i << ", " << j << endl;
gen[++tp] = i;
put(i, j);
put(i, j + 2);
put(i + 2, j + 2);
put(i + 2, j);
}
}
L(i, 1, tp) {
int x = gen[i];
int y = sum - gen[i];
if(i < tp && gen[i] + 1 == gen[i + 1]) {
put(x, y + 1);
put(x + 1, y);
put(x + 1, y + 2);
put(x + 2, y - 1);
put(x + 2, y + 1);
put(x + 3, y);
ans = (ll) ans * 2 % mod;
++i;
} else {
vector < pair < int, int > > VC;
VC.emplace_back(x, y + 1);
VC.emplace_back(x + 1, y);
VC.emplace_back(x + 1, y + 2);
VC.emplace_back(x + 2, y + 1);
int ok = 0;
L(p, 0, 3) {
if(s[VC[p].first][VC[p].second] == '1') {
ok = 1;
L(i, 0, 3)
if(i != p)
put(VC[i].first, VC[i].second);
// cout<<"okay put."<<endl;
break;
}
}
if(ok) continue;
put(x + 1, y);
put(x, y + 1);
if(s[x + 1][y + 1] == '0') {
put(x + 1, y + 1);
put(x + 2, y + 1);
put(x + 1, y + 2);
put(x + 1, y + 3);
put(x + 2, y + 3);
put(x + 3, y + 1);
put(x + 3, y + 2);
put(x + 3, y + 3);
ans = (ll) ans * 2 % mod;
} else {
rt[sum + 3].emplace_back(x + 1, x + 2);
}
}
}
// cout<<endl;
// L(i, 1, n) {
// L(j, 1, m) {
// cout<<s[i][j];
// S[i][j]=s[i][j];
// }
// cout<<endl;
// }
// cout<<endl;
}
cout << ans << '\n';
return 0;
}
/*
8 11
11111000111
11111010001
10001000101
00001110001
00001111000
00000000010
11101001000
11101000011
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 3416kb
input:
4 4 0001 0000 0000 1000
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: 0
Accepted
time: 2ms
memory: 3540kb
input:
5 4 0001 0101 0000 1010 1000
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3500kb
input:
3 3 111 111 111
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 1ms
memory: 3408kb
input:
3 4 1111 1111 1111
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 2ms
memory: 3420kb
input:
3 1000 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: 0
Accepted
time: 2ms
memory: 3416kb
input:
4 3 111 111 111 111
output:
1
result:
ok 1 number(s): "1"
Test #7:
score: 0
Accepted
time: 2ms
memory: 3476kb
input:
4 4 1111 1111 1111 1111
output:
1
result:
ok 1 number(s): "1"
Test #8:
score: 0
Accepted
time: 2ms
memory: 3468kb
input:
4 1000 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
1
result:
ok 1 number(s): "1"
Test #9:
score: 0
Accepted
time: 2ms
memory: 7328kb
input:
1000 3 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 1...
output:
1
result:
ok 1 number(s): "1"
Test #10:
score: 0
Accepted
time: 2ms
memory: 7376kb
input:
1000 4 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 111...
output:
1
result:
ok 1 number(s): "1"
Test #11:
score: 0
Accepted
time: 1ms
memory: 7328kb
input:
1000 1000 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
1
result:
ok 1 number(s): "1"
Test #12:
score: 0
Accepted
time: 2ms
memory: 3472kb
input:
3 3 000 010 010
output:
1
result:
ok 1 number(s): "1"
Test #13:
score: 0
Accepted
time: 2ms
memory: 3460kb
input:
3 3 000 011 000
output:
1
result:
ok 1 number(s): "1"
Test #14:
score: 0
Accepted
time: 2ms
memory: 3468kb
input:
3 3 010 010 000
output:
1
result:
ok 1 number(s): "1"
Test #15:
score: 0
Accepted
time: 2ms
memory: 3484kb
input:
3 3 000 110 000
output:
1
result:
ok 1 number(s): "1"
Test #16:
score: 0
Accepted
time: 2ms
memory: 3524kb
input:
4 4 1000 0000 0000 0001
output:
2
result:
ok 1 number(s): "2"
Test #17:
score: 0
Accepted
time: 0ms
memory: 3464kb
input:
4 4 0001 0000 0000 1000
output:
2
result:
ok 1 number(s): "2"
Test #18:
score: -100
Wrong Answer
time: 0ms
memory: 3452kb
input:
3 3 010 101 101
output:
result:
wrong answer Answer contains longer sequence [length = 1], but output contains 0 elements