QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#431910 | #6537. One, Two, Three | grass8cow | WA | 13ms | 34960kb | C++14 | 1.3kb | 2024-06-06 11:51:39 | 2024-06-06 11:51:40 |
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());
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