QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #422641 | #8090. Gurdurr | Afterlife# | AC ✓ | 897ms | 36192kb | C++20 | 2.9kb | 2024-05-27 17:52:09 | 2024-05-27 17:52:09 |
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(40 + 1);
for(int s = 0 ; s < (1<<i) ;s++) {
if(i == 0) sg[a][b][i][s] = 0;
else {
for(int j = 0;j <= i*2;j++) m[j] = 0;
sg[a][b][i][s] = -1;
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 <= 40;p++) {
if(!m[p]) {sg[a][b][i][s] = p ; break ;}
}
// assert(sg[a][b][i][s] != -1) ;
// 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() ;
}
详细
Test #1:
score: 100
Accepted
time: 854ms
memory: 36192kb
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: 868ms
memory: 35928kb
input:
1 3 II. .II III
output:
Second
result:
ok single line: 'Second'
Test #3:
score: 0
Accepted
time: 842ms
memory: 36148kb
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: 872ms
memory: 36152kb
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: 858ms
memory: 35920kb
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: 871ms
memory: 36040kb
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: 869ms
memory: 36012kb
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: 868ms
memory: 36104kb
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: 893ms
memory: 36056kb
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: 877ms
memory: 36068kb
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: 884ms
memory: 36056kb
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: 897ms
memory: 35964kb
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: 868ms
memory: 35920kb
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: 870ms
memory: 35920kb
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: 889ms
memory: 36076kb
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: 877ms
memory: 36088kb
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: 874ms
memory: 36192kb
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: 874ms
memory: 36072kb
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