QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #422628 | #8090. Gurdurr | Afterlife# | WA | 723ms | 36200kb | C++20 | 2.8kb | 2024-05-27 17:41:19 | 2024-05-27 17:41:20 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int n , m;
vector<int> sg[2][2][21];
void init() {
for(int i = 0;i <= 20;i++) {
for(int a = 0;a < 2;a++) { /// [0允许，1不允许]
for(int b = 0;b < 2;b++) {
sg[a][b][i].resize(1 << i) ;
vector<int> m(4);
for(int s = 0 ; s < (1<<i) ;s++) {
if(i == 0) sg[a][b][i][s] = 0;
else {
m[0] = m[1] = m[2] = m[3] = 0;
for(int j = 0;j < i;j++) {
if((s >> j) & 1) {
/// [3->4]
m[sg[a][0][j][s & ((1 << j) - 1)] ^ sg[0][b][i - j - 1][ (s & ((1 << i) - (1 << j+1))) >> j+1]] = 1;
/// [3->2]
m[sg[a][b][i][s ^ (1 << j)]] = 1;
}
else {
//// 2
//// [2->1]
if(!((j == 0 && a == 1) || (j == i - 1 && b == 1))) {
m[sg[a][1][j][s & ((1 << j) - 1)] ^ sg[1][b][i - j - 1][(s & ((1 << i) - (1 << j+1))) >> j+1]] = 1;
}
}
// printf("ok %d\n",j);
}
for(int p = 0;p <= 3;p++) {
if(!m[p]) {sg[a][b][i][s] = p ; break ;}
}
// printf("OK %d %d %d %d : %d\n",a,b,i,s , sg[a][b][i][s]);
}
}
}
}
// printf("OK %d\n",i);
}
}
void solv() {
int n ; cin >> n;
vector<array<int,4> > sub;
array<int,4> lst = {0,0,0,0};
for(int i = 1;i <= n;i++) {
string s;cin >> s;
if(s == "I.I") { /// 4
if(lst[2]) {
sub.push_back(lst) ;
}
lst = {0,0,0,0};
}
else if(s == ".I.") { ///1
lst[1] = 1 ;
sub.push_back(lst) ; lst = {0,0,0,0} ;
lst[0] = 1;
}
else if(s == "II." || s == ".II") { ///2
lst[3] += 0;
lst[2]++;
}
else {
lst[3] += (1 << lst[2]) ;
lst[2]++;
}
}
if(lst[2]) sub.push_back(lst);
int a = 0;
for(auto &x : sub) {
// printf("%d %d %d %d\n",x[0],x[1],x[2],x[3]);
a ^= sg[x[0]][x[1]][x[2]][x[3]];
}
if(a) cout << "First\n";
else cout << "Second\n";
}
int main() {
ios::sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0) ;
init() ;
int t;cin >> t;
while(t--) solv() ;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 716ms
memory: 36180kb
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: 723ms
memory: 36064kb
input:
1 3 II. .II III
output:
Second
result:
ok single line: 'Second'
Test #3:
score: 0
Accepted
time: 723ms
memory: 36044kb
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: -100
Wrong Answer
time: 718ms
memory: 36200kb
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:
wrong answer 76th lines differ - expected: 'Second', found: 'First'