QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#424934 | #6537. One, Two, Three | Bronya | WA | 0ms | 22308kb | C++20 | 2.3kb | 2024-05-29 20:00:42 | 2024-05-29 20:00:43 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n;
int a[1000006];
int A[10],last[10];
int op,b[10][1000005];
int u[1000005],v[1000005],w[1000005],cnt2;
int id[1000005];
bool Solve(int x,int y){
bool pd=false;cnt2=0;//cerr<<x<<' '<<y<<endl;
if(x+y>min({A[2],A[1],A[3]}))return true;
for(int j=1;j<=x;j++){
int X=A[3]-x+j;//cerr<<x<<" "<<y<<" "<<b[1][j] <<" "<<b[3][X]<<endl;
if(b[1][j]>b[3][X])return true;
u[++cnt2]=b[1][j],v[cnt2]=b[3][X];
}
for(int j=1;j<=y;j++){
int X=A[1]-y+j;
if(b[3][j]>b[1][X])return true;
u[++cnt2]=b[3][j],v[cnt2]=b[1][X];
}
// cerr<<x<<" "<<y<<" "<<pd<<endl;
return false;
}
bool cmp(int x,int y){
return v[x]<v[y];
}
int lans[600005][3],now[600005][3];
bool check(){
for(int i=1;i<=cnt2;i++)id[i]=i;
sort(id+1,id+1+cnt2,cmp);
set<int>st;
for(int i=1;i<=A[2];i++)st.insert(b[2][i]);
for(int i=1;i<=cnt2;i++){
auto it=st.lower_bound(u[id[i]]);
// cerr<<u[id[i]] <<" "<<v[id[i]]<<endl;
if(it==st.end()||*it>v[id[i]])return false;
lans[i][0]=u[id[i]];
lans[i][1]=*it;
lans[i][2]=v[id[i]];
st.erase(it);
}
return true;
}
int cnt[600005][4];
int main(){
// freopen("triples.in","r",stdin);
// freopen("triples.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]),A[a[i]]++,b[a[i]][A[a[i]]]=i;
for(int i=1;i<=n;i++){
for(int j=1;j<=3;j++)cnt[i][j]=cnt[i-1][j];
cnt[i][a[i]]++;
}
int last=0,lima=n,limb=n,limab;
for(int i=1;i<=n;i++){
lima=min(lima,last+cnt[i][2]-cnt[i][3]+A[3]);
last=min(last,cnt[i][1]-cnt[i][2]);
}
last=0;
for(int i=1;i<=n;i++){
limb=min(limb,last+cnt[i][2]-cnt[i][1]+A[1]);
last=min(last,cnt[i][3]-cnt[i][2]);
}
last=0;
for(int i=1;i<=n;i++){
limab=min(limab,last+cnt[i][2]-cnt[i][1]+A[1]+A[3]-cnt[i][3]);
last=min(last,cnt[i][1]+cnt[i][3]-cnt[i][2]);
}
lima=min(lima,limab);
limb=min(limb,limab-lima);
Solve(lima,limb);
check();
printf("%d\n",cnt2);
for(int i=1;i<=cnt2;i++)printf("%d %d %d\n",lans[i][0]-1,lans[i][1]-1,lans[i][2]-1);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 22228kb
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: 14044kb
input:
6 2 1 3 1 3 2
output:
0
result:
ok count=0
Test #3:
score: 0
Accepted
time: 0ms
memory: 22308kb
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 47 1 18 48 2 20 72 3 27 77 4 29 78 6 30 81 7 39 85 10 46 88 12 51 98 13 54 117 16 60 119 17 67 120 19 71 125 21 79 132 25 84 133 26 87 145 28 92 146 32 97 151 33 99 164 34 105 171 35 113 180 36 128 184 37 138 191 38 144 192 40 148 193 41 162 199 42 167 217 43 168 218 44 176 220 45 181 223 4...
result:
ok count=499
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 14124kb
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:
0
result:
wrong answer the number of matches is different