Submission #563624

#TimeUsernameProblemLanguageResultExecution timeMemory
563624DymoSwap (BOI16_swap)C++14
0 / 100
1 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=4e5+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]; ll n; pll par[maxn]; ll valpre[maxn]; ll st[maxn]; void dfs(ll u,ll x) { a[u]=b[u]; if (x) par[u]=make_pair(b[u],u); if (u*2<=n) dfs(u*2,1); if (u*2+1<=n) dfs(u*2+1,1); } pll pt(pll p,ll u) { if (p.ss==u) return make_pair(base,-1); else return p; } void dfs1(ll u,ll mx) { if (u>mx) return ; if (st[u]==0) { } else if (st[u]==1) { swap(a[u],a[u*2]); if (par[u].ss!=u) par[u*2]=par[u]; } else if (st[u]==2) { swap(a[u],a[u*2+1]); ll h=min(a[u*2],a[u*2+1]); par[u*2]=min(make_pair(h,u),pt(par[u],u)); par[u*2+1]=min(make_pair(h,u),pt(par[u],u)); } else { swap(a[u],a[u*2+1]); if (st[u]==3) swap(a[u*2],a[u*2+1]); par[u*2]=min(pt(par[u],u),make_pair(a[u*2],u*2)); par[u*2+1]=min(pt(par[u],u),make_pair(a[u*2+1],u*2+1)); } dfs1(u*2,mx); dfs1(u*2+1,mx); } pll vals[maxn]; void dosth(ll x,ll y) { swap(a[x],a[y]); swap(pos[a[x]],pos[a[y]]); } void update(ll x,ll y,ll p) { swap(vals[p].ff,vals[p].ss); dosth(x,y); ll nw=x; do { nw/=2; if (nw==p) break; if (vals[nw].ff==vals[p].ss) { vals[nw].ff=vals[p].ff; } else { vals[nw].ss=vals[p].ff; } } while (nw!=p); nw=y; do { nw/=2; if (nw==p) break; if (vals[nw].ff==vals[p].ff) { vals[nw].ff=vals[p].ss; } else { vals[nw].ss=vals[p].ss; } } while (nw!=p); } 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); } cin>> n; for (int i=1; i<=n; i++) { cin>> a[i]; b[i]=a[i]; pos[a[i]]=i; par[i]=make_pair(a[i],i); // keep this value } for (ll 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); while (nw) { if (st[nw]==2&&a[i]==max(vals[nw].ff,vals[nw].ss)&&pos[max(vals[nw].ff,vals[nw].ss)]<pos[min(vals[nw].ff,vals[nw].ss)]) val1=min(val1,make_pair(min(vals[nw].ff,vals[nw].ss),nw)); nw/=2; } // cout <<i<<" wtf"<<endl; if (val.ff>val1.ff) { st[i]=0; if (val1.ss!=i) { ll nw=i; vector<ll> vt; vt.pb(nw); while (1) { ll h=nw/2; vt.pb(h); if (h==val1.ss) break; else nw=h; } reverse(vt.begin(),vt.end()); ll t=(vals[val1.ss].ss==val1.ff); ll t1=(vt[1]==(val1.ss*2+1)); ll p=val1.ss; if ((t^t1)==0) st[val1.ss]=4; else { update(pos[vals[val1.ss].ff],pos[vals[val1.ss].ss],p); st[val1.ss]=3; } for (int i=1; i+1<vt.size(); i++) { ll x=vt[i]; if (st[x]==2) { st[x]=(3+(vt[i+1]%2)); if (st[x]==3) { update(pos[vals[x].ff],pos[vals[x].ss],p); } } } } } else { if (val.ss==i*2) { st[i]=1; dosth(i,i*2); } else { st[i]=2; valpre[i]=a[i]; dosth(i,i*2+1); vals[i]=make_pair(a[i*2],a[i*2+1]); } } if (i==0) { cout <<i<<" wtf"<<endl; cout <<val.ff<<" "<<val.ss<<" "<<val1.ff<<" "<<val1.ss<<" chk1"<<endl; for (int i=1;i<=n;i++) { cout <<a[i]<<" "<<vals[i].ff<<" "<<vals[i].ss<<" "<<st[i]<<endl; } cout <<endl; // cout <<t<<" "<<t1<<" "<<val1.ss<<endl; // if (i==6) return 0; } /*for (int i=1;i<=n;i++) { cout <<a[i]<<" "; } cout <<endl;*/ } for (int i=1; i<=n; i++) { cout <<a[i]<<" "; } }

Compilation message (stderr)

swap.cpp: In function 'int main()':
swap.cpp:190:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  190 |                 for (int i=1; i+1<vt.size(); i++)
      |                               ~~~^~~~~~~~~~
swap.cpp:130:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |         freopen("test.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
swap.cpp:131:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |         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...