QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#53627 | #2102. Gra w kółko | Appleblue17# | WA | 3ms | 7728kb | C++14 | 3.5kb | 2022-10-05 15:34:06 | 2022-10-05 15:34:07 |
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,ct=0;
for(int i=siz-1;i>=0;i--){
if(f[i].n!=1){
st=i; ct++;
}
}
if(st==-1) return 0;
if(ct==1) return (f[st].col==0)?1:-1;
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_+=f[t].d+f[t].l;
d_+=f[r].d;
for(int t=l+1;t<=r;t+=2) d_-=f[t].d;
for(int t=l;t<=r;t+=2) n_+=f[t].n;
id=l-1;
g[++id]=((abc){d_,n_,f[r].l,f[r].col});
}
else{
for(int t=l+1;t<r;t++){
g[t].d=g[t].n=2;
if(t%2) g[t].l=0;
}
}
}
}
// 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>3) 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>3) 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;
if(white_1==0) return -1;
vector <abc> L,R;
for(int i=1;i<=id;i++) L.push_back(g[i]),R.push_back(g[i]);
int pos=black_pos,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;
}
pos=white_pos,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++) L[i].col^=1,R[i].col^=1;
return max(solve(L),solve(R));
}
}
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: 3ms
memory: 7716kb
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: -100
Wrong Answer
time: 3ms
memory: 7728kb
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 B B B
result:
wrong answer 2nd lines differ - expected: 'R', found: 'B'