Submission #226193

#	Time	Username	Problem	Language	Result	Execution time	Memory
226193		MKopchev	Swap (BOI16_swap)	C++14	100 / 100	697 ms	3704 KiB

swap

#include<bits/stdc++.h>
using namespace std;
const int nmax=2e5+42;

int n,inp[nmax];

int would_go(int pos,int val)
{
    if(2*pos>n)return pos;

    if(val<inp[2*pos]&&val<inp[2*pos+1])return pos;

    if(inp[2*pos]<val&&inp[2*pos]<inp[2*pos+1])return would_go(2*pos,val);

    int x=val,y=inp[2*pos];

    if(x>y)swap(x,y);

    if(would_go(2*pos,x)<would_go(2*pos+1,x))
    {
        if(val==x)return would_go(2*pos,val);
        return would_go(2*pos+1,val);
    }

    if(val==x)return would_go(2*pos+1,val);
    return would_go(2*pos,val);
}
int main()
{
    scanf("%i",&n);
    for(int i=1;i<=n;i++)scanf("%i",&inp[i]);

    inp[n+1]=n+1;

    for(int i=1;2*i+1<=n;i++)
    {
        if(inp[i]<inp[2*i]&&inp[i]<inp[2*i+1])continue;

        if(inp[2*i]<inp[i]&&inp[2*i]<inp[2*i+1]){swap(inp[i],inp[2*i]);continue;}

        int x=inp[i],y=inp[2*i],small=inp[2*i+1];

        if(x>y)swap(x,y);

        if(would_go(2*i,x)<would_go(2*i+1,x)){inp[2*i]=x;inp[2*i+1]=y;}
        else {inp[2*i]=y;inp[2*i+1]=x;}

        inp[i]=small;
    }
    if(n%2==0&&inp[n/2]>inp[n])swap(inp[n/2],inp[n]);

    for(int i=1;i<=n;i++)
    {
        printf("%i",inp[i]);
        if(i==n)printf("\n");
        else printf(" ");
    }
    return 0;
}

Compilation message (stderr)

swap.cpp: In function 'int main()':
swap.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&n);
     ~~~~~^~~~~~~~~
swap.cpp:31:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1;i<=n;i++)scanf("%i",&inp[i]);
                          ~~~~~^~~~~~~~~~~~~~

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