Submission #563541

#TimeUsernameProblemLanguageResultExecution timeMemory
563541DymoSwap (BOI16_swap)C++14
0 / 100
0 ms340 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pll pair<ll,ll> #define ff first #define ss second #define pb push_back #define endl "\n" mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); const ll maxn=2e5+10; const ll mod=1e9+7 ; const ll base=2e9; /// i believe myself /// goal 2/7 ll a[maxn]; ll b[maxn]; ll valnw[maxn]; ll pos[maxn]; bool dd[maxn]; ll par[maxn]; ll valp[maxn]; void dosth(ll i,ll j) { swap(a[i],a[j]); swap(pos[a[i]],pos[a[j]]); } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); if (fopen("t.inp","r")) { freopen("test.inp","r",stdin); freopen("test.out","w",stdout); } ll n; cin>> n; for (int i=1;i<=n;i++) { cin>> a[i]; pos[a[i]]=i; // keep this value } for (int i=1;i<=n;i++) { pll val=make_pair(base,-1); if (i*2<=n) val=min(val,make_pair(a[i*2],(ll)i*2)); if (i*2+1<=n) val=min(val,make_pair(a[i*2+1],(ll)i*2+1)); ll nw=i/2; pll val1=make_pair(a[i],i/2); ll pospar=-1; while (nw) { if (!dd[nw]) val1=min(val1,make_pair(valp[nw],(ll)nw)); if (a[i]==valp[nw]) { pospar=nw; } nw/=2; } if (val1.ff==a[i]) val1.ss=max(val1.ss,pospar); if (val.ff>val1.ff) { dosth(i,pos[val1.ff]); ll nw=i/2; while (nw!=val1.ss) { dd[nw]=1; } dd[nw]=1; } else { if (val.ss==i*2) { dd[i]=1; dosth(i,i*2); } else { valp[i]=min(a[i*2],a[i]); dosth(i,i*2+1); } } } for (int i=1;i<=n;i++) { cout <<a[i]<<" "; } }

Compilation message (stderr)

swap.cpp: In function 'int main()':
swap.cpp:41:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         freopen("test.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
swap.cpp:42:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         freopen("test.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#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...