QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#707137 | #5921. Erdős–Szekeres | d325 | 0 | 1ms | 7584kb | C++14 | 1.4kb | 2024-11-03 14:48:46 | 2024-11-03 14:48:47 |
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 '