Submission #1012390

#TimeUsernameProblemLanguageResultExecution timeMemory
1012390hengliaoSwap (BOI16_swap)C++17
0 / 100
1 ms604 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; for(auto &it:tree[i].st){ if(!used[it]){ mn=min(mn, it); } } /*while(tar>0){ ll took=0; for(auto &it:tree[tar].st){ if(!used[it]){ mn=min(mn, it); took++; } } if(tree[tar].stop || took>=2){ break; } tar/=2; }*/ //if(i==3) cout<<f<<'\n'; 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; } //tree[2*i].st.pb(f); for(auto &it:tree[i].st){ tree[2*i].st.pb(it); } } else{ //tree[2*i].st.pb(a[2*i+1]); //tree[i].st.pb(a[2*i]); for(auto &it:tree[i].st){ tree[2*i].st.pb(it); tree[2*i+1].st.pb(it); } tree[2*i+1].st.pb(a[2*i]); } //cout<<i<<' '<<mn<<'\n'; if(mn==inf){ return; } assert(mn!=inf); 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; }

Compilation message (stderr)

swap.cpp: In function 'void solve()':
swap.cpp:42:12: warning: unused variable 'tar' [-Wunused-variable]
   42 |         ll tar=i;
      |            ^~~
#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...