QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#707137#5921. Erdős–Szekeresd3250 1ms7584kbC++141.4kb2024-11-03 14:48:462024-11-03 14:48:47

Judging History

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

  • [2024-11-03 14:48:47]
  • 评测
  • 测评结果:0
  • 用时:1ms
  • 内存:7584kb
  • [2024-11-03 14:48:46]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10;
#define ll long long
int read(){
    int x=0,f=1;
    char ch=0;
    while(ch<'0'||ch>'9'){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(!(ch<'0'||ch>'9')){
        x=(x<<3)+(x<<1)+(ch-'0');
        ch=getchar();
    }
    return x*f;
}
int n;
int a[N],b[N];
int st[N];
int h[N],ne[N<<2],e[N<<2],idx,d[N];
void add(int a,int b){
    idx++;
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx;
    d[b]++;
}
queue<int> q;
int now;
int res[N];
int main(){
    // ios::sync_with_stdio(false);
    // freopen("in.in","r",stdin);
    // freopen("out.out","w",stdout);
    n=read();
    now=n;
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<=n;i++)b[i]=read();
    for(int i=1;i<=n;i++){
        if(st[a[i]])add(st[a[i]],i);
        if(a[i]!=1)add(i,st[a[i]-1]);
        st[a[i]]=i;
    }
    for(int i=1;i<=n;i++)st[i]=0;
    for(int i=n;i>=1;i--){
        if(st[b[i]])add(st[b[i]],i);
        if(b[i]!=1)add(i,st[b[i]-1]);
        st[b[i]]=i;
    }
    for(int i=1;i<=n;i++){
        if(!d[i])q.push(i);
    }
    while(q.size()){
        int t=q.front();
        // cout<<"&& "<<t<<" ";
        q.pop();
        res[t]=now--;
        for(auto i=h[t];i;i=ne[i]){
            int v=e[i];
            d[v]--;
            if(!d[v])q.push(v);
        }
    }
    for(int i=1;i<=n;i++)cout<<res[i]<<" ";
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 5612kb

input:

30
1
1
1
8
1 2 1 3 3 1 4 1
4 4 3 4 3 2 2 1
20
1 2 3 4 5 6 7 8 3 4 5 6 7 8 9 10 11 12 13 14
1 1 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1
20
1 2 3 4 5 6 7 8 9 1 2 3 4 5 7 8 9 10 11 12
2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1
20
1 2 3 4 5 6 7 8 9 10 11 11 12 13 14 15 16 17 18 11
1 1 1 1 1 1 1 1 1 1 3 2 2 2 2...

output:

30 26 25 29 0 0 0 28 0 0 27 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 

result:

wrong answer 1st lines differ - expected: 'Case #1: 1', found: '30 26 25 29 0 0 0 28 0 0 27 0 ... 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 '

Subtask #2:

score: 0
Wrong Answer

Test #2:

score: 0
Wrong Answer
time: 1ms
memory: 7584kb

input:

30
1789
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...

output:

30 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 

result:

wrong answer 1st lines differ - expected: 'Case #1: 446 448 450 452 454 4...8 1347 1346 1345 1344 1343 1342', found: '30 1 2 3 4 5 6 7 8 9 10 11 12 ... 20 21 22 23 24 25 26 27 28 29 '