QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#77368#4273. Good Gamehuzhaoyang0 79ms20856kbC++141.4kb2023-02-14 14:57:332023-02-14 14:57:37

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 14:57:37]
  • 评测
  • 测评结果:0
  • 用时:79ms
  • 内存:20856kb
  • [2023-02-14 14:57:33]
  • 提交

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