QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #422617 | #8090. Gurdurr | Afterlife# | WA | 726ms | 36136kb | C++20 | 3.5kb | 2024-05-27 17:32:04 | 2024-05-27 17:32:05 |
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
//// [3->4]
// printf("in %d : %d %d : %d\n",j , s&((1 << j) - 1) , (s & ((1 << i) - (1 << j+1))) >> j+1 , sg[0][b][i - j - 1][ (s & ((1 << i) - (1 << j+1))) >> j+1]);
m[sg[a][0][j][s & ((1 << j) - 1)] ^ sg[0][b][i - j - 1][ (s & ((1 << i) - (1 << j+1))) >> j+1]] = 1;
// printf("in %d : %d %d : %d\n",j , s^(1<<j) , sg[a][b][j][s ^ ()]
//// [3->2]
m[sg[a][b][i][s ^ (1 << j)]] = 1;
//// [3->1]
// if(!((j == 0 && a == 1) || (j == i - 1 && b == 1))) {
// m.push_back(sg[a][1][j][s & ((1 << j) - 1)] ^ sg[1][b][i - j - 1][s & ((1 << i) - (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] = (lst[3] << 1) ;
lst[2]++;
}
else {
lst[3] = (lst[3] << 1) | 1;
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: 726ms
memory: 36052kb
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: 718ms
memory: 36088kb
input:
1 3 II. .II III
output:
Second
result:
ok single line: 'Second'
Test #3:
score: -100
Wrong Answer
time: 718ms
memory: 36136kb
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 First First Second Second Second First Second First First Second First First First First First First First Second First Second...
result:
wrong answer 28th lines differ - expected: 'Second', found: 'First'