QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#431913#6537. One, Two, Threegrass8cowRE 3ms31964kbC++141.3kb2024-06-06 11:54:212024-06-06 11:54:22

Judging History

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

  • [2024-06-06 11:54:22]
  • 评测
  • 测评结果:RE
  • 用时:3ms
  • 内存:31964kb
  • [2024-06-06 11:54:21]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int n,a[1010000];
#define pb push_back
vector<int>p0,p1,p2;
int A,B,C,s[1001000][3];
int L[1010000],R[1010000],e,M[1001000];
vector<int>g[1001000];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]),a[i]--;
		for(int j=0;j<3;j++)
		s[i][j]=s[i-1][j]+(a[i]==j);
		if(a[i]==0)p0.pb(i);
		if(a[i]==1)p1.pb(i);
		if(a[i]==2)p2.pb(i);
	}
	A=B=C=min(min(p0.size(),p2.size()),p1.size());
	int t0=p0.size(),t2=p2.size();
	for(int i=0;i<C;i++)if(p0[i]>p2[t2-1-i]){A=i;break;}
	for(int i=0;i<C;i++)if(p2[i]>p0[t0-1-i]){B=i;break;}
	for(int l=0;l<=n;l++)for(int r=l;r<=n;r++){
		int a1=s[l][0]+(s[n][2]-s[r][2]),a2=s[l][2]+(s[n][0]-s[r][0]),e=s[r][1]-s[l][1];
		C=min(C,e+a1+a2),A=min(A,e+a1),B=min(B,e+a2);
		//max(X-a1,0)+max(Y-a2,0)<=s[r][1]-s[l][1]
	}
	C=min(C,A+B),B=min(B,C-A);
	printf("%d\n",A+B);
	for(int i=0;i<A;i++)L[++e]=p0[i],R[e]=p2[t2-1-i];
	for(int i=0;i<B;i++)L[++e]=p2[i],R[e]=p0[t0-1-i];
	for(int i=1;i<=e;i++)g[L[i]].pb(i);
	priority_queue<pair<int,int> >q;
	for(int i=1;i<=n;i++){
		for(int x:g[i])q.push({-R[x],x});
		if(a[i]==1&&!q.empty()){
			int o=q.top().second;q.pop();
			assert(i<=R[o]);
			M[o]=i;
		}
	}
	for(int i=1;i<=e;i++)assert(M[i]);
	for(int i=1;i<=e;i++)printf("%d %d %d\n",L[i]-1,M[i]-1,R[i]-1);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 31964kb

input:

6
3 1 2 2 3 1

output:

2
1 2 4
0 3 5

result:

ok count=2

Test #2:

score: 0
Accepted
time: 3ms
memory: 30900kb

input:

6
2 1 3 1 3 2

output:

0

result:

ok count=0

Test #3:

score: -100
Runtime Error

input:

3000
1 1 1 1 1 3 1 1 3 3 1 3 1 1 2 3 1 1 2 1 2 1 3 3 3 1 1 2 1 2 2 3 1 1 1 1 1 1 1 2 1 1 1 1 1 1 2 3 3 1 1 2 1 1 2 1 1 1 1 1 2 1 1 1 1 1 1 2 1 1 1 2 3 1 1 1 1 3 3 2 1 3 1 1 2 3 1 2 3 1 1 1 2 1 1 1 1 2 3 2 1 1 1 1 1 2 1 1 1 1 1 1 1 2 1 1 1 3 1 3 3 1 1 1 1 3 1 1 2 1 1 1 3 3 1 1 1 1 2 1 1 1 1 1 2 3 3 1...

output:


result: