QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #53651 | #2102. Gra w kółko | Appleblue17# | WA | 4ms | 13968kb | C++14 | 4.0kb | 2022-10-05 16:45:12 | 2022-10-05 16:45:13 |
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,col;
};
int pos[N],col[N],id;
abc f[N],g[N];
int solve(vector <abc> P){
int siz=P.size();
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]=f[st];
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_+=f[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;
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;
vector <abc> L,R;
for(int i=1;i<=id;i++) L.push_back(g[i]);
int pos=black_pos-1,lst=(pos+id-1)%id,nxt=(pos+1)%id;
if(L[pos].l){
L[nxt].d+=L[pos].l;
L[pos].l=0;
}
else{
L[lst].d+=L[lst].l;
L[lst].l=0;
}
for(int i=0;i<id;i++) L[i].col^=1;
if(white_1){
R.clear();
for(int i=1;i<=id;i++) R.push_back(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(L),-solve(R));
}
else return -solve(L);
}
}
int main(){
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;
}
if(!n){
puts("C");
continue;
}
if(!m){
puts("B");
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;
}
}
vector <abc> P;
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++;
P.push_back((abc){pos[r]-pos[l]+1,r-l+1,pos[r+1]-pos[r]-1,col[l]});
}
// for(auto x: P){
// cout<<x.d<<","<<x.n<<","<<x.l<<" ";
// }
// cout<<endl;
int ans=solve(P);
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: 13796kb
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: 2ms
memory: 13948kb
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: 4ms
memory: 13800kb
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: 2ms
memory: 13744kb
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: 4ms
memory: 13888kb
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: 4ms
memory: 13968kb
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: 13780kb
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: -100
Wrong Answer
time: 3ms
memory: 13884kb
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 C R B
result:
wrong answer 2nd lines differ - expected: 'R', found: 'C'