QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#425045#6537. One, Two, ThreeDaiRuiChen007WA 7ms32016kbC++141.2kb2024-05-29 21:41:572024-05-29 21:41:57

Judging History

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

  • [2024-05-29 21:41:57]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:32016kb
  • [2024-05-29 21:41:57]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int MAXN=6e5+5;
int A[MAXN],B[MAXN],C[MAXN],z[MAXN];
vector <int> f[4],o1[MAXN],o2[MAXN];
signed main() {
//	freopen("triples.in","r",stdin);
//	freopen("triples.out","w",stdout);
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;++i) {
		scanf("%d",&z[i]),f[z[i]].push_back(i);
		A[i]=A[i-1]+(z[i]==1);
		B[i]=B[i-1]+(z[i]==2);
		C[i]=C[i-1]+(z[i]==3);
	}
	int S=n,T=n,R=min(A[n],C[n]);
	for(int i=1,s=0,t=0,r=0;i<=n;++i) {
		R=min(R,A[n]-A[i]+C[n]-C[i]+B[i]+r);
		r=min(r,A[i]+C[i]-B[i]);
		S=min(S,C[n]-C[i]+B[i]+s);
		s=min(s,A[i]-B[i]);
		T=min(T,A[n]-A[i]+B[i]+t);
		t=min(t,C[i]-B[i]);
	}
	R=min(R,S+T),T=R-S;
	if(T<0) S-=T,T=0;
	printf("%d\n",R);
	for(int i=0;i<S;++i) o1[f[1][i]].push_back(f[3][C[n]-S+i]);
	for(int i=0;i<T;++i) o2[f[3][i]].push_back(f[1][A[n]-T+i]);
	deque <array<int,2>> q1,q2; 
	for(int i=1;i<=n;++i) {
		for(int x:o1[i]) q1.push_back({x,i});
		for(int x:o2[i]) q2.push_back({x,i});
		if(z[i]==2&&(q1.size()||q2.size())) {
			array <int,2> w;
			if(q2.empty()||q1[0]<q2[0]) w=q1[0],q1.pop_front();
			else w=q2[0],q2.pop_front();
			printf("%d %d %d\n",w[1]-1,i-1,w[0]-1);
		}
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 7ms
memory: 32016kb

input:

6
3 1 2 2 3 1

output:

2
1 2 4
-1 3 -1

result:

wrong answer invalid triple