QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#431919#6537. One, Two, Threegrass8cowWA 15ms34412kbC++141.4kb2024-06-06 12:02:202024-06-06 12:02:21

Judging History

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

  • [2024-06-06 12:02:21]
  • 评测
  • 测评结果:WA
  • 用时:15ms
  • 内存:34412kb
  • [2024-06-06 12:02:20]
  • 提交

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());
	for(int i=0;i<=n;i++)A=min(A,s[i][0]+s[n][2]-s[i][2]);
	for(int i=0;i<=n;i++)B=min(B,s[i][2]+s[n][0]-s[i][0]);
	int t0=p0.size(),t2=p2.size();
	for(int i=0;i<C;i++)if(p0[i]>p2[t2-1-i]){A=min(A,i);break;}
	for(int i=0;i<C;i++)if(p2[i]>p0[t0-1-i]){B=min(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-A+i];
	for(int i=0;i<B;i++)L[++e]=p2[i],R[e]=p0[t0-B+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;
}

详细

Test #1:

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

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

input:

6
2 1 3 1 3 2

output:

0

result:

ok count=0

Test #3:

score: 0
Accepted
time: 8ms
memory: 34412kb

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 14 604
1 18 607
2 20 616
3 27 624
4 29 627
6 30 639
7 39 651
10 46 661
12 51 673
13 54 681
16 60 687
17 67 697
19 71 699
21 79 704
25 84 706
26 87 714
28 92 727
32 97 728
33 99 730
34 105 735
35 113 736
36 128 740
37 138 743
38 144 744
40 148 747
41 162 750
42 167 754
43 168 755
44 176 758
45 ...

result:

ok count=499

Test #4:

score: 0
Accepted
time: 15ms
memory: 31688kb

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

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

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 3 542
1 7 544
2 8 545
4 9 547
5 10 550
6 11 554
12 17 557
13 21 558
15 22 559
19 23 563
24 25 564
26 27 566
28 33 570
29 34 573
31 35 576
36 42 577
37 50 580
39 51 581
40 53 582
45 54 599
47 55 601
48 56 602
52 57 607
58 59 608
66 70 609
69 73 611
77 589 613
78 594 619
80 595 728
82 596 729
86...

result:

wrong answer the number of matches is different