QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #526842 | #8090. Gurdurr | Vermeil | AC ✓ | 1864ms | 89852kb | C++17 | 2.4kb | 2024-08-21 22:10:03 | 2024-08-21 22:10:03 |
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 (n == 1){
return bit + 1;
}
if (dp[n][bit] != -1) return dp[n][bit];
vector<int> g;
dp[n][bit] = 0;
for (int i=0;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));
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
if (n - i - 2 > 0) gn ^= f(n - i - 2, bit >> (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: 4ms
memory: 89612kb
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: 4ms
memory: 89844kb
input:
1 3 II. .II III
output:
Second
result:
ok single line: 'Second'
Test #3:
score: 0
Accepted
time: 3ms
memory: 89848kb
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:
ok 292 lines
Test #4:
score: 0
Accepted
time: 0ms
memory: 89780kb
input:
4216 3 .II I.I I.I 4 .I. III .I. I.I 1 III 3 .II I.I III 4 .II I.I .I. III 3 I.I I.I I.I 6 III III III .I. II. III 6 I.I II. II. II. .II II. 2 I.I .I. 3 .I. II. .II 3 I.I I.I III 6 I.I I.I .I. I.I I.I I.I 4 I.I I.I .I. II. 2 .II I.I 5 .II .I. I.I .I. .II 2 II. II. 1 .II 4 I.I III .I. .II 3 .II II. I...
output:
First First First First Second Second First First Second First First Second Second First Second First First First First First Second Second Second Second First First First Second Second First Second Second Second First Second First First First Second First First Second First Second Second First Firs...
result:
ok 4216 lines
Test #5:
score: 0
Accepted
time: 12ms
memory: 89616kb
input:
30000 7 .I. I.I III .I. I.I .I. III 3 III .I. II. 4 I.I I.I III III 1 II. 1 .I. 2 II. .I. 6 .I. I.I .I. .II II. II. 7 II. .I. I.I .I. I.I .II I.I 3 .I. .II .I. 7 III I.I .II III .II .II III 2 .II I.I 3 III I.I .I. 7 I.I I.I .I. II. .I. III III 6 I.I I.I II. .I. II. I.I 6 III III I.I .I. I.I .II 7 II...
output:
Second First First First Second Second First First Second First First First First Second Second First First First First First Second First First First First First First First First First First First First First Second First Second First Second First First Second First Second First First Second First...
result:
ok 30000 lines
Test #6:
score: 0
Accepted
time: 20ms
memory: 89852kb
input:
30000 9 .I. I.I .I. I.I .I. I.I .I. I.I .I. 7 .II III III II. I.I I.I .II 3 .I. I.I I.I 1 .I. 2 II. II. 10 III .I. I.I .II .II III .II I.I .I. .II 2 .I. I.I 10 .I. I.I .I. I.I .I. I.I I.I .I. I.I .I. 10 .I. III III II. I.I III .I. I.I II. .I. 3 I.I .I. .II 10 .II .I. .II .II II. .II III .I. .II .I. ...
output:
Second First Second Second First Second Second Second Second Second First First Second Second First Second Second Second First First First First First First Second Second First First First First Second Second First First Second First Second Second First Second Second First First Second First First F...
result:
ok 30000 lines
Test #7:
score: 0
Accepted
time: 19ms
memory: 89628kb
input:
30000 12 I.I .I. III III .II .I. I.I III III II. III III 7 III II. .I. III .I. .II II. 2 III III 7 I.I .I. II. .II II. .I. II. 6 III III I.I II. III .II 10 .I. I.I III .I. .II I.I I.I III .II III 7 .II I.I .I. III .I. III III 11 II. I.I III .I. II. .I. III III III II. I.I 5 III .I. I.I .II III 2 I.I...
output:
First First First First Second Second First First First Second Second First Second First First Second First First First First First First First First First Second First First First Second First Second First Second First First Second Second First First First First First First First First First First ...
result:
ok 30000 lines
Test #8:
score: 0
Accepted
time: 32ms
memory: 89512kb
input:
30000 12 II. III II. II. I.I I.I I.I III III .II I.I I.I 3 .I. III .I. 7 .I. I.I .I. I.I .I. I.I .I. 10 II. II. .II III .II .II .II II. .I. .II 14 III .I. III I.I II. .I. III III II. .II .I. II. II. III 1 III 8 I.I III III III III .I. I.I III 1 I.I 3 I.I I.I .I. 8 .I. III I.I I.I I.I .II III .I. 7 ....
output:
First First Second First First First Second Second Second First First First First First First First First First First First Second Second Second Second First Second First First First Second First Second First First First First First First First First Second Second First Second First Second First Sec...
result:
ok 30000 lines
Test #9:
score: 0
Accepted
time: 93ms
memory: 89800kb
input:
30000 11 .I. III II. .I. II. I.I II. .II I.I .I. III 13 .I. .II III .II III III III .I. II. .I. III .II III 2 II. III 10 III II. III III II. I.I I.I III .I. III 3 I.I .II .II 16 II. .II .II III II. III III II. .II .II II. II. III III III II. 7 III .II III III III III III 14 .I. III .I. III III III I...
output:
First First Second First First Second First Second Second First First First First First First First Second Second Second Second First First First Second First First First Second First First Second Second Second First First First First First First First First First Second First Second First First Sec...
result:
ok 30000 lines
Test #10:
score: 0
Accepted
time: 344ms
memory: 89652kb
input:
30000 6 III .II .I. III II. .I. 6 I.I .I. .II I.I .I. I.I 1 III 1 II. 3 I.I I.I I.I 15 I.I I.I I.I I.I .I. I.I .I. I.I I.I I.I .I. I.I I.I .I. I.I 2 I.I I.I 12 III .I. III I.I .I. .II .I. I.I .I. I.I I.I .II 9 .I. I.I III III III III .I. III .I. 13 .I. I.I .I. III .II .II III .II .II I.I III III .I....
output:
First Second First First Second Second Second First First First First Second First First First First Second First Second First First First Second Second First First First Second Second Second First Second First First First First Second First Second First First Second First First First Second Second ...
result:
ok 30000 lines
Test #11:
score: 0
Accepted
time: 28ms
memory: 89640kb
input:
30000 11 .I. .II .I. I.I II. .I. II. .I. III .I. I.I 13 III III .II II. .I. I.I .II III I.I .II I.I .I. I.I 18 .II .I. II. II. I.I II. .I. III .II I.I .I. .II III I.I .I. II. II. III 18 .I. III .I. III III II. III I.I I.I .I. I.I III .II III .I. III .II II. 4 I.I III .I. III 15 II. .I. III III .II I...
output:
First First First Second Second Second First First Second First First First Second First First First Second First First First Second First Second First Second First Second Second Second First First First Second First Second First Second First Second Second First First First First First First First F...
result:
ok 30000 lines
Test #12:
score: 0
Accepted
time: 1757ms
memory: 89576kb
input:
30000 11 .II III II. II. .II II. III II. II. II. II. 17 III II. II. II. II. II. .II II. III II. III III .II III .II .II .II 11 III III III III III III III II. III II. III 14 III III III III III III III III III II. III III .II III 9 III .II II. III .II II. III III .II 8 III II. .II III III II. .II .I...
output:
First First Second Second First First First Second First First Second First First First First First First First First First First First Second First First First Second First Second First First First First First First First First Second First First Second Second Second Second First First First First ...
result:
ok 30000 lines
Test #13:
score: 0
Accepted
time: 1703ms
memory: 89580kb
input:
30000 16 II. III III III I.I III III III III III III III .II III III III 18 I.I I.I I.I I.I I.I I.I II. .II .II II. I.I .I. I.I I.I .I. I.I .II I.I 17 III III II. II. .II .II II. .II .II .II II. III .II .II .II II. .II 6 I.I I.I I.I II. I.I I.I 2 III .I. 1 I.I 5 II. I.I I.I I.I .I. 8 .II II. III I.I...
output:
Second First First First First Second First First First First First Second Second First Second First Second First Second First Second First Second Second Second First Second Second First First First Second First First First First Second Second First First Second Second Second Second First Second Sec...
result:
ok 30000 lines
Test #14:
score: 0
Accepted
time: 1803ms
memory: 89588kb
input:
30000 3 .II .II .II 11 III I.I .I. I.I III I.I II. .I. .II I.I I.I 7 .II I.I I.I I.I I.I III .I. 17 III I.I .II II. III I.I .I. III III I.I .I. I.I III I.I I.I II. I.I 6 III II. .II III I.I .II 4 II. III III .I. 8 III III III III .II III .II III 17 .II .II .II II. III II. II. III II. .II II. .II II....
output:
First Second Second First First First First First First First Second First First First First First First First First First First First Second Second First First Second First Second Second First First Second First Second First First First First Second First Second First First Second Second Second Fir...
result:
ok 30000 lines
Test #15:
score: 0
Accepted
time: 1801ms
memory: 89644kb
input:
30000 17 II. III .II III III III .II .II III II. III III .II III .II II. III 1 III 15 III I.I .II III III III .II .II II. II. I.I .II .I. .II II. 10 .II II. II. III II. II. .II II. II. II. 5 .II II. II. .II II. 8 I.I .I. III III .II .II III I.I 19 .II .II II. II. .II .II .II .II II. .II .II II. .II ...
output:
First First Second Second First First First Second First First First First First First First First Second First First First First First First First First First First First First Second First Second First Second First First First Second First First First First First First First First First First Firs...
result:
ok 30000 lines
Test #16:
score: 0
Accepted
time: 1768ms
memory: 89624kb
input:
30000 11 I.I .I. I.I .I. I.I .I. III I.I I.I .I. I.I 6 .I. II. .II .I. III I.I 11 III I.I I.I .I. III III I.I I.I .II .II I.I 12 III III I.I .I. III II. .I. I.I I.I I.I III I.I 4 .I. III .I. II. 9 III .I. III .I. I.I .I. .II .I. III 5 III .I. I.I II. I.I 15 .II III .II I.I II. .I. II. I.I III III .I...
output:
First First Second First First First Second First First First First First First First First Second First Second First Second First First First Second First First First Second Second First Second Second Second First Second First Second Second First Second Second Second First Second First First Second...
result:
ok 30000 lines
Test #17:
score: 0
Accepted
time: 1864ms
memory: 89552kb
input:
30000 2 III II. 12 I.I II. II. II. II. III .I. III I.I III I.I .II 17 .II III III III III III III .II III III III III III III III .II .II 17 .I. I.I .I. I.I .I. I.I .I. I.I I.I .I. I.I .I. I.I .I. I.I .I. I.I 4 .I. .II III II. 6 .II III II. .II III III 6 III II. II. I.I .I. I.I 2 .II III 18 III III ...
output:
Second First First Second Second First Second Second First Second First Second First Second Second First First Second First First First First First Second Second First First First First First Second Second Second Second First First First Second Second First First First First First First First First ...
result:
ok 30000 lines
Test #18:
score: 0
Accepted
time: 1839ms
memory: 89560kb
input:
30000 2 .II II. 1 .II 9 .II I.I III II. II. I.I III .I. I.I 11 .II II. III II. III II. .II .II I.I .I. II. 11 II. I.I III II. .I. III .II .I. III .I. II. 1 .II 1 III 5 .I. I.I III I.I .II 7 III I.I III .I. III II. I.I 8 III III .I. .II II. II. .II .II 17 I.I III III .I. II. I.I .II I.I .I. .II III ....
output:
First First Second First First First First First First First First First Second Second First First First Second First First First First Second First Second First First Second First First First First First First First First First First First First First First First First Second First First Second Fir...
result:
ok 30000 lines