Submission #563766

#	Time	Username	Problem	Language	Result	Execution time	Memory
563766		Dymo	Swap (BOI16_swap)	C++14	100 / 100	52 ms	9068 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;

ll n;
ll a[maxn];
ll st[maxn];
ll get(ll u)
{
   if (st[u]==0) return a[u];
   else if (u%2==1)
   {
       assert(st[u]==1);
       if (st[u-1]==0) return get(u/2);
       else if (st[u-1]==1) return a[u-1];
       else if (st[u-1]==2) return min(get(u/2),a[u-1]);
   }
   else
   {
       if (st[u]==1)
       {
           return get(u/2);
       }
       else
       {
           return min(get(u/2),a[u]);
       }
   }
}
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);
    }
    memset(a,0x3f,sizeof(a));
   // cout <<a[0]<<endl;
    cin>> n;
    for (int i=1;i<=n;i++)
    {
        cin>> a[i];
    }
    for (int i=1;i<=n;i++)
    {
        pll val=min(make_pair(a[i*2],i*2),make_pair(a[i*2+1],i*2+1));
        ll valnw=get(i);
      //  cout <<valnw<<" "<<val.ff<<" "<<val.ss<<" chk1"<<endl;
      /*if (i==2)
      {
          cout <<valnw<<" "<<i<<" "<<st[i]<<" "<<a[i]<<" "<<i/2<<" "<<st[i/2]<<" "<<a[i/2]<<endl;
      }*/
        if (val.ff>valnw)
        {
            cout <<valnw<<" ";
            ll u=i;
            while (1)
            {
                if (st[u]==0) break;
                else if (u%2==1)
                {
                    assert(st[u]==1);
                    if (st[u-1]==0)
                    {
                        u/=2;
                    }
                    else if (st[u-1]==1)
                    {
                        assert(valnw==a[u-1]);
                        break;
                    }
                    else if (st[u-1]==2)
                    {
                        if (valnw==a[u-1])
                        {
                            st[u-1]=1;
                            break;
                        }
                        st[u-1]=0;
                        u/=2;
                    }
                }
                else
                {
                    if (st[u]==2)
                    {
                        if (a[u]==valnw)
                        {
                            st[u]=0;
                            break;
                        }
                        else
                        {
                            st[u]=1;
                            u/=2;
                        }
                    }
                    else
                    {
                        u/=2;
                    }
                }
            }
            st[i*2]=0;
            st[i*2+1]=0;
        }
        else
        {
            cout <<val.ff<<" ";
            if (val.ss==i*2)
            {
                st[i*2]=1;
                st[i*2+1]=0;
            }
            else
            {
                st[i*2]=2;
                st[i*2+1]=1;
            }
        }
    }
}

Compilation message (stderr)

swap.cpp: In function 'long long int get(long long int)':
swap.cpp:40:1: warning: control reaches end of non-void function [-Wreturn-type]
   40 | }
      | ^
swap.cpp: In function 'int main()':
swap.cpp:48:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |         freopen("test.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
swap.cpp:49:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         freopen("test.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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