QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#53751 | #2102. Gra w kółko | Appleblue17# | WA | 2ms | 3764kb | C++14 | 3.9kb | 2022-10-05 21:35:44 | 2022-10-05 21:35:49 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int T,len,n,m;
int a[N],b[N];
struct abc{
int d,n,l;
bool col;
};
int pos[N*2],id;
bool col[N*2];
abc f[N*2],g[N];
int solve(abc P[N],int siz){
for(int i=0;i<siz;i++) f[i+siz]=f[i]=P[i];
// cout<<"sol: \n";
// for(int i=0;i<siz;i++) cout<<"("<<f[i].col<<")"<<f[i].d<<","<<f[i].n<<","<<f[i].l<<" ";
// cout<<endl;
int st=-1;
for(int i=0;i<siz;i++){
if(f[i].n!=1){
st=i;
break;
}
}
if(st==-1) return 0;
id=0;
for(int i=st;i<st+siz;i++){
g[++id]=f[i];
if(id>1 && g[id].n>1 && g[id-1].n==1){
int r=id,l=id-1;
while(g[l].n==1) l--;
if((r-l)%2==0){
int d_=0,n_=0;
for(int t=l;t<r;t++) d_+=g[t].d+g[t].l;
d_+=g[r].d;
for(int t=l+1;t<=r;t+=2) d_-=g[t].d;
for(int t=l;t<=r;t+=2) n_+=g[t].n;
id=l-1;
g[++id]=((abc){d_,n_,g[r].l,g[r].col});
}
else{
for(int t=l+1;t<r;t++){
g[t].d=g[t].n=2;
if((t-l)%2) g[t].l=0;
}
}
}
}
if(g[id].n==1){
g[++id]=g[1];
int r=id,l=id-1;
while(g[l].n==1) l--;
if((r-l)%2==0){
int d_=0,n_=0;
for(int t=l;t<r;t++) d_+=g[t].d+g[t].l;
d_+=g[r].d;
for(int t=l+1;t<=r;t+=2) d_-=g[t].d;
for(int t=l;t<=r;t+=2) n_+=g[t].n;
id=l-1;
g[++id]=((abc){d_,n_,g[r].l,g[r].col});
}
else{
for(int t=l+1;t<r;t++){
g[t].d=g[t].n=2;
if((t-l)%2) g[t].l=0;
}
}
if(l>1){
for(int i=1;i<id;i++) g[i]=g[i+1];
id--;
}
}
// for(int i=1;i<=id;i++) cout<<"("<<g[i].col<<")"<<g[i].d<<","<<g[i].n<<","<<g[i].l<<" ";
// cout<<endl;
if(id==1) return (g[1].col)?-1:1;
int black_=0,black_2=0,black_1=0,black_pos,white_=0,white_1=0,white_pos;
for(int i=1;i<=id;i++){
int lst=(i==1)?(id):(i-1);
if(g[i].n<3) continue;
if(g[i].col){
if(g[i].d>g[i].n) black_++;
else if(g[lst].l && g[i].l) black_2++;
else if(g[lst].l || g[i].l) black_1++,black_pos=i;
}
else{
if(g[i].d>g[i].n) white_++;
else if(g[lst].l || g[i].l) white_1++,white_pos=i;
}
}
if(black_ || black_2 || black_1>=2){
if(white_ || white_1) return 0;
else return -1;
}
else if(black_1==0){
if(white_ || white_1) return 1;
else{
int s=0;
for(int i=1;i<=id;i++) s^=g[i].l;
if(s==0) return -1;
else return 1;
}
}
else if(black_1==1){
if(white_ || white_1>=2) return 1;
int tot=-1;
abc R[N];
for(int i=1;i<=id;i++) f[i-1]=g[i];
int pos=black_pos-1,lst=(pos+id-1)%id,nxt=(pos+1)%id;
if(f[pos].l){
f[nxt].d+=f[pos].l;
f[pos].l=0;
}
else{
f[lst].d+=f[lst].l;
f[lst].l=0;
}
for(int i=0;i<id;i++) f[i].col^=1;
if(white_1){
for(int i=1;i<=id;i++) R[i-1]=g[i];
pos=white_pos-1,lst=(pos+id-1)%id,nxt=(pos+1)%id;
if(R[pos].l){
R[pos].d+=R[pos].l;
R[pos].l=0;
}
else{
R[pos].d+=R[lst].l;
R[lst].l=0;
}
for(int i=0;i<id;i++) R[i].col^=1;
return max(-solve(f,id),-solve(R,id));
}
else return -solve(f,id);
}
}
int main(){
// freopen("1.txt","r",stdin);
cin>>T;
while(T--){
cin>>len>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=m;i++) cin>>b[i];
if(n+m==len){
puts("C");
continue;
}
id=0;
int p=1,q=1;
while(p<=n && q<=m){
if(a[p]<b[q]) pos[++id]=a[p],col[id]=0,p++;
else pos[++id]=b[q],col[id]=1,q++;
}
while(p<=n) pos[++id]=a[p],col[id]=0,p++;
while(q<=m) pos[++id]=b[q],col[id]=1,q++;
int st=0;
for(int i=2;i<=id;i++){
if(col[i]!=col[i-1]){
st=i;
break;
}
}
int pid=0;
for(int i=1;i<=id;i++) pos[i+id]=pos[i]+len,col[i+id]=col[i];
for(int l=st,r;l<st+id;l=r+1){
r=l;
while(col[r+1]==col[l]) r++;
f[pid++]=(abc){pos[r]-pos[l]+1,r-l+1,pos[r+1]-pos[r]-1,col[l]};
}
int ans=solve(f,pid);
if(ans==1) puts("B");
else if(ans==-1) puts("C");
else if(ans==0) puts("R");
}
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 3536kb
input:
4 11 3 3 3 8 11 1 6 9 11 4 7 2 7 8 11 1 3 4 5 6 9 10 11 1 5 10 1 3 6 8 11 11 2 4 9 11 1 7 8 10
output:
R C C C
result:
ok 4 lines
Test #2:
score: 0
Accepted
time: 1ms
memory: 3548kb
input:
4 11 4 2 1 3 5 6 2 4 13 5 5 3 6 7 8 10 1 2 4 9 13 11 5 1 2 5 7 8 11 10 13 6 4 1 2 4 5 6 7 3 8 9 10
output:
B R B B
result:
ok 4 lines
Test #3:
score: 0
Accepted
time: 1ms
memory: 3488kb
input:
4 13 6 3 3 4 5 11 12 13 1 8 9 11 4 2 2 4 5 11 1 3 13 4 5 4 8 11 13 2 3 6 7 9 13 4 4 1 7 9 12 2 5 8 10
output:
B B C C
result:
ok 4 lines
Test #4:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
4 13 5 4 1 2 9 11 13 3 5 6 10 13 5 4 1 2 7 11 12 3 5 8 13 13 4 5 2 3 6 12 4 5 7 8 13 11 1 5 5 2 3 4 6 7
output:
R B C C
result:
ok 4 lines
Test #5:
score: 0
Accepted
time: 0ms
memory: 3484kb
input:
4 13 3 6 1 2 11 7 8 9 10 12 13 13 5 4 4 5 7 8 12 1 2 11 13 13 4 4 5 7 10 11 1 6 8 13 11 2 4 5 10 1 4 8 11
output:
B B B C
result:
ok 4 lines
Test #6:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
4 13 5 5 4 8 10 11 12 1 2 3 5 9 11 4 2 1 5 9 10 8 11 13 5 4 1 3 4 6 12 5 9 10 11 13 5 4 1 9 11 12 13 3 4 8 10
output:
B B B R
result:
ok 4 lines
Test #7:
score: 0
Accepted
time: 2ms
memory: 3716kb
input:
4 15 5 5 1 2 6 11 15 3 4 5 10 14 15 5 5 3 4 5 9 15 1 7 11 12 13 15 5 5 1 6 7 8 10 3 4 5 9 15 15 6 1 1 2 4 5 6 15 3
output:
C R C B
result:
ok 4 lines
Test #8:
score: 0
Accepted
time: 2ms
memory: 3624kb
input:
4 15 3 5 7 9 11 6 8 10 12 13 15 5 5 7 10 11 13 14 1 3 5 8 12 15 5 5 1 3 9 14 15 2 4 5 6 10 15 5 5 1 3 6 11 15 2 4 8 10 12
output:
C R R B
result:
ok 4 lines
Test #9:
score: 0
Accepted
time: 1ms
memory: 3764kb
input:
4 15 6 4 2 3 6 13 14 15 1 4 7 12 15 4 3 1 5 13 14 3 9 15 15 6 4 2 3 4 6 7 15 1 5 12 13 15 8 7 1 2 4 5 7 9 14 15 3 6 8 10 11 12 13
output:
C B B C
result:
ok 4 lines
Test #10:
score: -100
Wrong Answer
time: 2ms
memory: 3720kb
input:
5 15 4 4 2 5 9 12 4 6 10 14 15 3 6 7 11 14 2 3 4 6 9 12 15 5 5 1 2 6 9 15 5 8 12 13 14 15 5 5 8 9 12 13 15 4 5 6 11 14 15 5 5 1 2 5 6 11 3 7 8 9 12
output:
R C R R B
result:
wrong answer 3rd lines differ - expected: 'B', found: 'R'