QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#431913 | #6537. One, Two, Three | grass8cow | RE | 3ms | 31964kb | C++14 | 1.3kb | 2024-06-06 11:54:21 | 2024-06-06 11:54:22 |
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();
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: 31964kb
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: 30900kb
input:
6 2 1 3 1 3 2
output:
0
result:
ok count=0
Test #3:
score: -100
Runtime Error
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...