제출 #729668

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
729668		Rafi22	Swap (BOI16_swap)	C++14	100 / 100	70 ms	7548 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;
                }
                if(is[2*x]==1) break;
            }
            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;
                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;
                    }
                    is[2*x]=2;
                }
                else
                {
                    if(k==x)
                    {
                        is[x]=2;
                        break;
                    }
                }
            }
            is[2*i]=2;
            is[2*i+1]=2;
        }
        else if(c==a[2*i])
        {
            is[2*i]=1;
            is[2*i+1]=2;
        }
        else is[2*i+1]=1;
    }

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

swap.cpp: In function 'int main()':
swap.cpp:90:21: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
   90 |                     if(k==2*x)
      |                     ^~

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