QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#77368 | #4273. Good Game | huzhaoyang | 0 | 79ms | 20856kb | C++14 | 1.4kb | 2023-02-14 14:57:33 | 2023-02-14 14:57:37 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
int n,m,a[N],pre[N],nex[N];
char s[N];
vector<pair<int,int> >ans;
bool check(int l,int r){
int mid=(l+r>>1);
int x=max(pre[mid],l),y=min(nex[mid],r);
return (y-x<=(r-l>>1));
}
void clr(int l,int r){
int len=r-l+1;
for(int i=r-1;i>l+1;i-=2)ans.push_back(make_pair(i,2));
ans.push_back(make_pair(l,2+(len&1)));
}
void work(int l,int r){
int mid=(l+r>>1),s=0;
int x=max(pre[mid],l),y=min(nex[mid],r);
for(int i=1;i<y;i++)s+=a[i];
if (x<mid){
clr(s+1,s+a[y]);
for(int i=1;i<mid-x;i++){
clr(s-a[y-i]+1,s+a[y+i]);
s-=a[y-i];
}
}
s=0;
for(int i=1;i<x;i++)s+=a[i];
clr(s+1,s+a[x]);
for(int i=1;i<=x-l;i++){
clr(s-a[x-i]+1,s+a[x+i]);
s-=a[x-i];
}
}
int main(){
scanf("%d%s",&n,s+1);
for(int i=1,j=1;i<=n;i=j){
while ((j<=n)&&(s[i]==s[j]))j++;
a[++m]=j-i;
}
for(int i=1;i<=m;i++)pre[i]=(a[i]>1 ? i : pre[i-1]);
nex[m+1]=m+1;
for(int i=m;i;i--)nex[i]=(a[i]>1 ? i : nex[i+1]);
if (m&1){
if (check(1,m))work(1,m);
else{
puts("-1");
return 0;
}
}
else{
bool flag=0;
for(int i=1;i<=m;i+=2)
if ((check(1,i))&&(check(i+1,m))){
int s=0;
for(int j=1;j<=i;j++)s+=a[j];
flag=1,work(i+1,m),work(1,i);
break;
}
if (!flag){
puts("-1");
return 0;
}
}
printf("%d\n",ans.size());
for(pair<int,int>i:ans)printf("%d %d\n",i.first,i.second);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 3
Accepted
time: 3ms
memory: 7520kb
input:
9 ABAABBBAA
output:
4 3 2 4 2 2 2 1 3
result:
ok good solution!
Test #2:
score: -3
Wrong Answer
time: 3ms
memory: 5536kb
input:
13 ABABBABABBABA
output:
6 9 2 8 2 4 2 3 2 2 2 1 2
result:
wrong answer invalid operation on step #6: AB
Subtask #2:
score: 0
Wrong Answer
Test #51:
score: 0
Wrong Answer
time: 3ms
memory: 7608kb
input:
299 ABABABABABABABABABABABABABABABABABBAABBAABBAABBAAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBBAABBAABBAABBAABBAABBAABBAABBAABBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...
output:
133 167 2 167 2 165 2 165 2 163 2 163 2 161 2 161 2 159 2 159 2 157 2 157 2 155 2 155 2 153 2 153 2 151 2 151 2 149 2 149 2 147 2 147 2 145 2 145 2 143 2 143 2 141 2 141 2 139 2 139 2 137 2 138 2 135 3 135 2 133 2 133 2 131 2 131 2 129 2 129 2 127 2 127 2 125 2 125 2 123 2 123 2 121 2 121 2 119 2 11...
result:
wrong answer wrong solution (expected NO SOLUTION)
Subtask #3:
score: 0
Wrong Answer
Test #102:
score: 0
Wrong Answer
time: 3ms
memory: 5676kb
input:
5998 BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...
output:
2998 4002 2 4000 2 3998 2 3995 3 3994 2 3993 2 3992 2 3991 2 3990 2 3989 2 3988 2 3987 2 3986 2 3985 2 3984 2 3983 2 3982 2 3981 2 3980 2 3979 2 3978 2 3977 2 3976 2 3975 2 3974 2 3973 2 3972 2 3971 2 3970 2 3969 2 3968 2 3967 2 3966 2 3965 2 3964 2 3963 2 3962 2 3961 2 3960 2 3959 2 3958 2 3957 2 3...
result:
wrong answer invalid operation on step #2002: BA
Subtask #4:
score: 0
Wrong Answer
Test #153:
score: 0
Wrong Answer
time: 79ms
memory: 20856kb
input:
999997 ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...
output:
499998 666669 2 666667 2 666665 2 666663 2 666661 2 666660 2 666659 2 666658 2 666657 2 666656 2 666655 2 666654 2 666653 2 666652 2 666651 2 666650 2 666649 2 666648 2 666647 2 666646 2 666645 2 666644 2 666643 2 666642 2 666641 2 666640 2 666639 2 666638 2 666637 2 666636 2 666635 2 666634 2 66663...
result:
wrong answer invalid operation on step #333336: AB