QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#127965 | #5077. Card Game | batrr# | WA | 4ms | 17072kb | C++17 | 3.8kb | 2023-07-20 13:21:41 | 2023-07-20 13:21:42 |
Judging History
answer
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
const int N = 300500, inf = 1e9, mod = 998244353;
const ll INF = 1e18;
int sum(int a, int b) {
a += b;
if (a >= mod)
a -= mod;
return a;
}
int sub(int a, int b) {
a -= b;
if (a < 0)
a += mod;
return a;
}
int mult(int a, int b) {
return 1ll * a * b % mod;
}
int bp(int a, int b) {
int res = 1;
while (b) {
if (b & 1)
res = mult(res, a);
a = mult(a, a);
b >>= 1;
}
return res;
}
int inv(int x) {
return bp(x, mod - 2);
}
int n, m;
string s[N];
pii val[30][30], emp = {-1, -1};
int timer, was[30][30][30][30];
int dp[30][30][30][30];
int tt, wt[N];
//char F = 'B';
char F = 'R';
int get(int xl, int xr, int yl, int yr) {
if (xl > xr || yl > yr)
return 0;
if (was[xl][xr][yl][yr] == timer)
return dp[xl][xr][yl][yr];
was[xl][xr][yl][yr] = timer;
int res = 0;
for (int x = xl; x <= xr; x++) {
for (int y = yl; y <= yr; y++) {
if (val[x][y] == emp)
continue;
int cur = 0;
if (s[val[x][y].f][val[x][y].s] == 'G') {
cur ^= get(xl, x - 1, yl, y - 1);
cur ^= get(x + 1, xr, yl, y - 1);
cur ^= get(xl, x - 1, y + 1, yr);
cur ^= get(x + 1, xr, y + 1, yr);
} else if (s[val[x][y].f][val[x][y].s] == F) {
cur ^= get(xl, x - 1, yl, yr);
cur ^= get(x + 1, xr, yl, yr);
} else {
cur ^= get(xl, xr, yl, y - 1);
cur ^= get(xl, xr, y + 1, yr);
}
}
}
tt++;
for (int x = xl; x <= xr; x++) {
for (int y = yl; y <= yr; y++) {
if (val[x][y] == emp)
continue;
int cur = 0;
if (s[val[x][y].f][val[x][y].s] == 'G') {
cur ^= get(xl, x - 1, yl, y - 1);
cur ^= get(x + 1, xr, yl, y - 1);
cur ^= get(xl, x - 1, y + 1, yr);
cur ^= get(x + 1, xr, y + 1, yr);
} else if (s[val[x][y].f][val[x][y].s] == F) {
cur ^= get(xl, x - 1, yl, yr);
cur ^= get(x + 1, xr, yl, yr);
} else {
cur ^= get(xl, xr, yl, y - 1);
cur ^= get(xl, xr, y + 1, yr);
}
wt[cur] = tt;
}
}
while(wt[res] == tt)
res++;
return dp[xl][xr][yl][xr] = res;
}
void solve() {
cin >> n >> m;
if(n == 1 || m == 1){
if((n + m) % 2 == 1)
cout << "L\n";
else
cout << "W\n";
return;
}
for (int i = 0; i < n; i++)
cin >> s[i];
int ans = 0;
for (int it = 0; it < 2; it++) {
timer++;
for (int i = 0; i < 30; i++)
for (int j = 0; j < 30; j++)
val[i][j] = emp;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if ((i ^ j ^ it) & 1) {
int x = i + j;
int y = i - j + m;
x /= 2;
y /= 2;
val[x][y] = {i, j};
}
ans ^= get(0, 29, 0, 29);
}
if (ans == 0)
cout << "L\n";
else
cout << "W\n";
}
int main() {
#ifdef DEBUG
freopen("input.txt", "r", stdin);
#endif
ios_base::sync_with_stdio(false);
int t = 1;
// cin >> t;
for (int i = 1; i <= t; i++) {
// cout << "Case #" << i << endl;
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 14304kb
input:
1 3 BBB
output:
W
result:
ok single line: 'W'
Test #2:
score: 0
Accepted
time: 3ms
memory: 16876kb
input:
2 3 BBG RGR
output:
W
result:
ok single line: 'W'
Test #3:
score: 0
Accepted
time: 4ms
memory: 14128kb
input:
2 2 GG GG
output:
L
result:
ok single line: 'L'
Test #4:
score: 0
Accepted
time: 1ms
memory: 14876kb
input:
1 10 RRRRRRRRRR
output:
L
result:
ok single line: 'L'
Test #5:
score: 0
Accepted
time: 1ms
memory: 13212kb
input:
1 11 BBBBBBBBBBB
output:
W
result:
ok single line: 'W'
Test #6:
score: 0
Accepted
time: 3ms
memory: 13668kb
input:
10 1 G G G G G G G G G G
output:
L
result:
ok single line: 'L'
Test #7:
score: 0
Accepted
time: 0ms
memory: 14036kb
input:
11 1 R R R R R R R R R R R
output:
W
result:
ok single line: 'W'
Test #8:
score: -100
Wrong Answer
time: 3ms
memory: 17072kb
input:
2 20 BBGGBGBGGBBGGBGGBGGG GGBBBGBGBBBGBGGGGGGG
output:
W
result:
wrong answer 1st lines differ - expected: 'L', found: 'W'