Submission #563614

#	Time	Username	Problem	Language	Result	Execution time	Memory
563614		Dymo	Swap (BOI16_swap)	C++14	0 / 100	1090 ms	340 KiB

swap

#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 (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 (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("test.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) val1=min(val1,make_pair(min(vals[nw].ff,vals[nw].ss),nw));
            nw/=2;
        }
      //if (i==4)  cout <<val.ff<<" "<<val.ss<<" "<<val1.ff<<" "<<val1.ss<<" chk1"<<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));

                if ((t^t1)==0)
                    st[val1.ss]=4;
                else
                {
                    st[val1.ss]=3;
                }
                //if (i==4) cout <<t<<" "<<t1<<" chkwtf"<<endl;
                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 (i==4)
                {
                    for (auto to:vt) cout <<to<<" "<<st[to]<<" chk4"<<endl;
                }*/
                ll p=val1.ss;
                for (int i=0;i+1<vt.size();i++)
                {
                    if (st[vt[i]]==3)
                    {
                        ll x=pos[vals[vt[i]].ff];
                        ll y=pos[vals[vt[i]].ss];
                        update(x,y,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]);
            }
        }
        /*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:181:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  181 |                 for (int i=1; i+1<vt.size(); i++)
      |                               ~~~^~~~~~~~~~
swap.cpp:194:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  194 |                 for (int i=0;i+1<vt.size();i++)
      |                              ~~~^~~~~~~~~~
swap.cpp:126:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |         freopen("test.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
swap.cpp:127:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |         freopen("test.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 11
• Subtask 3: 0 / 27
• Subtask 4: 0 / 20
• Subtask 5: 0 / 32