Submission #64535

#TimeUsernameProblemLanguageResultExecution timeMemory
64535zetapiSwap (BOI16_swap)C++14
0 / 100
3 ms640 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define mp make_pair #define int long long #define itr ::iterator typedef pair<int,int> pii; const int MAX=1e6; int N,arr[MAX]; map<pii,int> dp; int get(int X,int val) //get the minimum index possible { if(dp.count(mp(X,val))) return dp[mp(X,val)]; else if(2*X>N) return dp[mp(X,val)]=X; else if(2*X+1>N) { if(arr[2*X]<val) return dp[mp(X,val)]=2*X; else return dp[mp(X,val)]=X; } else if(val<arr[2*X] and val<arr[2*X+1]) return dp[mp(X,val)]=X; else if(arr[2*X+1]<val) { if(arr[2*X]<arr[2*X+1]) return dp[mp(X,val)]=get(2*X,val); else return min(get(2*X,val),get(2*X+1,val)); } else if(arr[2*X]<val) return dp[mp(X,val)]=get(2*X,val); } void solve(int X) { if(2*X>N) return ; else if(2*X+1>N) { if(arr[2*X]<arr[X]) swap(arr[2*X],arr[X]); return ; } else if(arr[2*X+1]<arr[X]) { if(arr[2*X]<arr[2*X+1]) { swap(arr[X],arr[2*X]); return ; } swap(arr[X],arr[2*X+1]); int mn=min(arr[2*X],arr[2*X+1]); int mx=max(arr[2*X],arr[2*X+1]); if(get(2*X,mn)<get(2*X+1,mn)) { arr[2*X]=mn; arr[2*X+1]=mx; } else { arr[2*X]=mx; arr[2*X+1]=mn; } //cout<<2*X<<" "<<mn<<" "<<get(2*X,mn)<<"\n"; //cout<<2*X+1<<" "<<mn<<" "<<get(2*X+1,mn)<<"\n"; return ; } else if(arr[2*X]<arr[X]) swap(arr[X],arr[2*X]); return ; } signed main() { ios_base::sync_with_stdio(false); cin>>N; for(int A=1;A<=N;A++) cin>>arr[A]; for(int A=1;A<=N;A++) solve(A); for(int A=1;A<=N;A++) cout<<arr[A]<<" "; return 0; }

Compilation message (stderr)

swap.cpp: In function 'long long int get(long long int, long long int)':
swap.cpp:41:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
#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...