QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#424934#6537. One, Two, ThreeBronyaWA 0ms22308kbC++202.3kb2024-05-29 20:00:422024-05-29 20:00:43

Judging History

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

  • [2024-05-29 20:00:43]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:22308kb
  • [2024-05-29 20:00:42]
  • 提交

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;
}

详细

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