QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#77370 | #4273. Good Game | huzhaoyang | 0 | 79ms | 20748kb | C++14 | 1.5kb | 2023-02-14 15:00:55 | 2023-02-14 15:00:56 |
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];
int k=mid-x;
if (k){
clr(s+1,s+a[y]);
for(int i=1;i<k;i++){
clr(s-a[y-i]+1,s+a[y+i]);
s-=a[y-i];
}
a[y-k]+=a[y+k];
for(int i=y+k+1;i<=r;i++)a[y-k+(i-y-k)]=a[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;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 3
Accepted
time: 3ms
memory: 5556kb
input:
9 ABAABBBAA
output:
4 3 2 4 2 2 2 1 3
result:
ok good solution!
Test #2:
score: 0
Accepted
time: 3ms
memory: 7600kb
input:
13 ABABBABABBABA
output:
6 9 2 8 2 4 2 3 2 2 3 1 2
result:
ok good solution!
Test #3:
score: 0
Accepted
time: 3ms
memory: 7540kb
input:
15 AABABAABABAABAB
output:
7 11 2 10 2 6 2 5 2 4 3 3 2 1 2
result:
ok good solution!
Test #4:
score: -3
Wrong Answer
time: 2ms
memory: 5500kb
input:
15 ABAABBBABAABBAB
output:
7 10 2 9 3 5 3 5 2 3 2 2 2 1 3
result:
wrong answer invalid operation on step #7: out of bounds
Subtask #2:
score: 0
Wrong Answer
Test #51:
score: 0
Wrong Answer
time: 0ms
memory: 7584kb
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: 7
Accepted
time: 3ms
memory: 5636kb
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:
ok good solution!
Test #103:
score: 0
Accepted
time: 4ms
memory: 7668kb
input:
5999 BBBBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...
output:
2998 4003 2 4000 3 3999 2 3998 2 3997 2 3996 2 3995 2 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 3...
result:
ok good solution!
Test #104:
score: -7
Wrong Answer
time: 3ms
memory: 5660kb
input:
5998 ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...
output:
2998 4497 3 4496 3 4495 2 4494 2 4493 2 4492 2 4491 2 4490 2 4489 2 4488 2 4487 2 4486 2 4485 2 4484 2 4483 2 4482 2 4481 2 4480 2 4479 2 4478 2 4477 2 4476 2 4475 2 4474 2 4473 2 4472 2 4471 2 4470 2 4469 2 4468 2 4467 2 4466 2 4465 2 4464 2 4463 2 4462 2 4461 2 4460 2 4459 2 4458 2 4457 2 4456 2 4...
result:
wrong answer invalid operation on step #2998: out of bounds
Subtask #4:
score: 0
Wrong Answer
Test #153:
score: 9
Accepted
time: 79ms
memory: 20068kb
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:
ok good solution!
Test #154:
score: 0
Accepted
time: 60ms
memory: 20748kb
input:
999998 BBBBBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...
output:
499998 666670 2 666667 3 666666 2 666665 2 666664 2 666663 2 666662 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 66663...
result:
ok good solution!
Test #155:
score: -9
Wrong Answer
time: 78ms
memory: 20020kb
input:
999997 BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...
output:
499997 749997 2 749996 3 749995 2 749994 2 749993 2 749992 2 749991 2 749990 2 749989 2 749988 2 749987 2 749986 2 749985 2 749984 2 749983 2 749982 2 749981 2 749980 2 749979 2 749978 2 749977 2 749976 2 749975 2 749974 2 749973 2 749972 2 749971 2 749970 2 749969 2 749968 2 749967 2 749966 2 74996...
result:
wrong answer invalid operation on step #499997: out of bounds