QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#431910#6537. One, Two, Threegrass8cowWA 13ms34960kbC++141.3kb2024-06-06 11:51:392024-06-06 11:51:40

Judging History

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

  • [2024-06-06 11:51:40]
  • 评测
  • 测评结果:WA
  • 用时:13ms
  • 内存:34960kb
  • [2024-06-06 11:51:39]
  • 提交

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();
			M[o]=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: 8ms
memory: 32688kb

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: 0ms
memory: 29408kb

input:

6
2 1 3 1 3 2

output:

0

result:

ok count=0

Test #3:

score: 0
Accepted
time: 11ms
memory: 34960kb

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:

499
0 2997 2999
1 2886 2985
2 2857 2978
3 2806 2970
4 2767 2963
6 2766 2962
7 2743 2956
10 2737 2954
12 2719 2951
13 14 2940
16 2617 2934
17 18 2931
19 20 2930
21 2583 2927
25 30 2921
26 27 2919
28 29 2913
32 2482 2909
33 2481 2908
34 2412 2899
35 2317 2883
36 2246 2865
37 2213 2858
38 39 2853
40 21...

result:

ok count=499

Test #4:

score: 0
Accepted
time: 13ms
memory: 32008kb

input:

3000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

1
0 1374 2901

result:

ok count=1

Test #5:

score: 0
Accepted
time: 7ms
memory: 32372kb

input:

3000
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2...

output:

1
1755 1756 2819

result:

ok count=1

Test #6:

score: -100
Wrong Answer
time: 5ms
memory: 32296kb

input:

1500
1 1 1 2 1 1 1 2 2 2 2 2 1 1 3 1 2 2 3 1 2 2 2 2 1 2 1 2 1 1 3 1 2 2 2 2 1 1 3 1 1 2 2 3 2 1 3 1 1 2 2 2 1 2 2 2 2 2 1 2 3 2 3 2 3 2 1 3 2 1 2 3 2 2 3 2 3 1 1 3 1 3 1 3 3 3 1 3 3 3 1 1 3 1 3 1 3 1 1 1 3 1 3 1 3 3 1 1 1 3 1 1 3 1 1 1 1 1 3 3 3 3 1 3 1 1 1 1 3 3 3 3 3 3 1 3 1 1 1 3 1 3 1 1 1 1 3 1...

output:

494
0 11 1499
1 10 1497
2 3 1496
4 9 1493
5 8 1492
6 7 1491
12 21 1490
13 17 1489
15 16 1487
19 20 1484
24 25 1480
26 27 1478
28 34 1477
29 33 1475
31 32 1473
36 54 1467
37 44 1466
39 42 1465
40 41 1464
45 51 1462
47 50 1461
48 49 1460
52 53 1456
58 59 1455
66 68 1454
69 70 1453
77 1339 1451
78 1336...

result:

wrong answer the number of matches is different