QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#77370#4273. Good Gamehuzhaoyang0 79ms20748kbC++141.5kb2023-02-14 15:00:552023-02-14 15:00:56

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-14 15:00:56]
  • 评测
  • 测评结果:0
  • 用时:79ms
  • 内存:20748kb
  • [2023-02-14 15:00:55]
  • 提交

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;
}

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: 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