Submission #900568

#TimeUsernameProblemLanguageResultExecution timeMemory
900568pccPermutation Recovery (info1cup17_permutation)C++17
25 / 100
1 ms3932 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pll pair<ll,ll> #define pii pair<int,int> #define fs first #define sc second #define tlll tuple<ll,ll,ll> #define ls treap[now].pl #define rs treap[now].pr #define int ll const int mxn = 7e4+10; struct node{ int pl,pr; ll sum,pri,val; node(){ val = pl = pr = sum = pri = 0; } }; node treap[mxn]; int arr[mxn]; int n; int ppp = 0; int newnode(){ return ++ppp; } void pull(int now){ treap[now].sum = treap[ls].sum+treap[rs].sum+treap[now].val; return; } int merge(int a,int b){ if(!a)return b; if(!b)return a; if(treap[a].pri>treap[b].pri){ treap[a].pr = merge(treap[a].pr,b); pull(a); return a; } else{ treap[b].pl = merge(a,treap[b].pl); pull(b); return b; } } void split(int now,int &a,int &b,int tar){ if(!now){ a = b = 0; return; } if(treap[now].val+treap[ls].sum == tar){ a = now,b = rs; treap[now].pr = 0; } else if(treap[ls].sum>=tar){ b = now; split(ls,a,treap[b].pl,tar); } else{ a = now; split(rs,treap[a].pr,b,tar-treap[ls].sum-treap[now].val); } pull(a); pull(b); return; } int ans[mxn]; int C = 0; void dfs(int now){ if(!now)return; dfs(ls); ans[now] = ++C; dfs(rs); return; } void pv(int now){ if(!now)return; pv(ls); cout<<now<<','; pv(rs); return; } main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>n; int rt = 1; for(int i = 1;i<=n;i++){ cin>>arr[i]; treap[i].pri = (rand()<<15)|rand(); } treap[1].sum = treap[1].val = 1; for(int i = 2;i<=n;i++){ int l,r; split(rt,l,r,arr[i]-arr[i-1]-1); treap[i].sum = treap[i].val = arr[i]-arr[i-1]; //cout<<i<<":"<<endl;pv(rt);cout<<endl; //cout<<i<<":"<<endl;pv(l);cout<<endl;pv(r);cout<<endl; rt = merge(l,i); rt = merge(rt,r); } dfs(rt); for(int i = 1;i<=n;i++)cout<<ans[i]<<' '; }

Compilation message (stderr)

permutation.cpp:95:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   95 | main(){
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...