QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #526827 | #8090. Gurdurr | Vermeil | WA | 3ms | 89788kb | C++17 | 2.4kb | 2024-08-21 21:21:26 | 2024-08-21 21:21:27 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
int getType(string s){
if (s == "II." || s == ".II") return 0;
if (s == "III") return 1;
if (s == "I.I") return 2;
return 3;
}
int dp[21][1<<20];
int f(int n, int bit){
if (n <= 0) return 0;
if (dp[n][bit] != -1) return dp[n][bit];
vector<int> g;
dp[n][bit] = 0;
for (int i=0,l,r;i<n;i++){
if (bit & (1 << i)){
// III -> II.
g.push_back(f(n, bit ^ (1 << i)));
// III -> I.I
int gn = 0;
gn ^= f(i, bit & ((1 << i) - 1));
gn ^= f(n - i - 1, (bit >> (i + 1)) << (i + 1));
g.push_back(gn);
}
else{
// II. -> .I.
int gn = 0;
if (i + 1 < n && bit & (1 << (i + 1))) gn ^= 1; // left III
if (i - 1 >= 0 && bit & (1 << (i - 1))) gn ^= 1; // right III
gn ^= f(n - i - 2, (bit >> (i + 2)) << (i + 2));
if (i - 1 >= 0) gn ^= f(i - 1, bit & ((1 << (i - 1)) - 1));
g.push_back(gn);
}
}
sort(g.begin(), g.end());
for (int i: g){
if (i == dp[n][bit]) dp[n][bit]++;
}
return dp[n][bit];
}
signed main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int tc = 1;
for (int i=0;i<=20;i++)fill(dp[i],dp[i]+(1<<20),-1);
cin>>tc;
while(tc--){
int n;cin>>n;
vector<string> s(n);
vector<int> v(n);
vector<bool> sep(n, false);
int ans = 0;
for (int i=0;i<n;i++){
cin>>s[i];
v[i] = getType(s[i]);
if (v[i] >= 2) sep[i] = true;
if (v[i] == 3){
if (i - 1 >= 0) sep[i - 1] = true;
if (i + 1 < n) sep[i + 1] = true;
}
}
int nb = 0;
int c = 0;
for (int i=0;i<n;i++){
if (sep[i]){
if (v[i] == 1) ans ^= 1;
ans ^= f(c, nb);
nb = 0;
c = 0;
}
else{
c++;
nb <<= 1;
nb |= v[i];
}
}
ans ^= f(c, nb);
if (ans)cout<<"First\n";
else cout<<"Second\n";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 89500kb
input:
5 1 III 1 I.I 1 .I. 1 .II 2 III III
output:
First Second Second First First
result:
ok 5 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 89560kb
input:
1 3 II. .II III
output:
Second
result:
ok single line: 'Second'
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 89788kb
input:
292 4 III II. III .I. 2 III I.I 1 .I. 1 I.I 2 III III 3 I.I .I. III 3 II. III I.I 4 III III III III 2 .II .I. 4 .I. .II III .I. 4 I.I .I. I.I III 4 III .I. II. .I. 4 III I.I III I.I 3 III III III 4 III I.I II. .II 2 .I. III 4 III I.I .I. I.I 3 .II .II I.I 3 .I. I.I I.I 4 I.I III I.I III 1 III 4 .I. ...
output:
First First Second Second First First Second Second Second First First First Second First First First First First Second Second First Second Second First First Second Second Second First Second Second Second First Second First First Second First First Second First First First First Second First Firs...
result:
wrong answer 63rd lines differ - expected: 'Second', found: 'First'