QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#431919 | #6537. One, Two, Three | grass8cow | WA | 15ms | 34412kb | C++14 | 1.4kb | 2024-06-06 12:02:20 | 2024-06-06 12:02:21 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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