Submission #1012352

#TimeUsernameProblemLanguageResultExecution timeMemory
1012352hengliaoSwap (BOI16_swap)C++17
0 / 100
1 ms856 KiB
#include<bits/stdc++.h> #include <chrono> #include <random> using namespace std; #define F first #define S second #define pb push_back #define vll vector<ll> #define pll pair<ll, ll> typedef long long ll; struct node{ vll st; bool stop; node(){ stop=0; } }; const ll mxN=2e5+5; const ll inf=1e18; vector<node> tree; ll n; ll a[mxN]; bool used[mxN]; void solve(){ memset(used, 0, sizeof(used)); cin>>n; for(ll i=1;i<=n;i++){ cin>>a[i]; } tree.resize(n+1); for(ll i=1;i<=n;i++){ tree[i].st.pb(a[i]); } vll ans(n+1); for(ll i=1;i<=n;i++){ ll tar=i; ll mn=inf; ll type=1; while(tar>0){ if(tree[tar].stop){ break; } for(auto &it:tree[tar].st){ if(!used[it]){ mn=min(mn, it); } } tar/=2; } if(2*i<=n){ if(a[2*i]<mn){ type=2; mn=a[2*i]; } } if(2*i+1<=n){ if(a[2*i+1]<mn){ type=3; mn=a[2*i+1]; } } if(type==1){ if(2*i<=n){ tree[2*i].stop=1; } if(2*i+1<=n){ tree[2*i+1].stop=1; } } else if(type==2){ if(2*i+1<=n){ tree[2*i+1].stop=1; } } else{ tree[2*i].st.pb(a[2*i+1]); tree[2*i+1].st.pb(a[2*i]); } ans[i]=mn; used[mn]=1; } for(ll i=1;i<=n;i++){ cout<<ans[i]<<' '; } cout<<'\n'; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); solve(); return 0; }
#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...