QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #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;
}
详细
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'