Submission #729653

#	Time	Username	Problem	Language	Result	Execution time	Memory
729653		Rafi22	Swap (BOI16_swap)	C++14	0 / 100	0 ms	212 KiB

swap

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
ll mod=998244353;
int inf=1000000007;
ll infl=1000000000000000007;

const int N=200007;

int a[4*N];
int is[4*N];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=n+1;i<=4*n;i++) a[i]=inf;
    for(int i=1;i<=n;i++)
    {
        int mn=inf,k,x=i;
        if(is[i]!=1&&is[2*i]!=1&&is[2*i+1]!=1)
        {
            mn=a[i];
            k=i;
        }
        while(x>1)
        {
            //cout<<i<<" "<<x<<" "<<is[x]<<endl;
            if(is[x]==2) break;
            bool L=x%2;
            x/=2;
            if(L)
            {
                if(is[2*x]!=1&&is[x]!=1&&mn>a[x])
                {
                    mn=a[x];
                    k=x;
                }
                if(is[2*x]!=2&&mn>a[2*x])
                {
                    mn=a[2*x];
                    k=2*x;
                }
            }
            else
            {
                if(is[x]!=1&&mn>a[x])
                {
                    mn=a[x];
                    k=x;
                }
            }
        }
        int c=min({mn,a[2*i],a[2*i+1]});
        cout<<c<<" ";
        if(c==mn)
        {
            x=i;
            if(k==i)
            {
                is[i]=2;
                is[2*i]=2;
                is[2*i+1]=2;
                x=0;
            }
            while(x>1)
            {
                is[x]=1;
                bool L=x%2;
                x/=2;
                if(L)
                {
                    if(k==x)
                    {
                        is[2*x]=2;
                        is[x]=2;
                        break;
                    }
                    if(k==2*x)
                    {
                        is[2*x]=1;
                        break;
                    }
                }
                else
                {
                    if(k==x)
                    {
                        is[x]=2;
                        break;
                    }
                }
            }
        }
        else if(c==a[2*i])
        {
            is[2*i]=1;
            is[2*i+1]=2;
        }
        else is[2*i+1]=1;
    }

    return 0;
}

Compilation message (stderr)

swap.cpp: In function 'int main()':
swap.cpp:101:30: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
  101 |                         is[x]=2;
      |                         ~~~~~^~

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