Submission #1029654

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029654		MMihalev	Swap (BOI16_swap)	C++14	0 / 100	0 ms	348 KiB

swap

#include<iostream>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<tuple>
#include<set>
#include<map>
#include<random>
#include<chrono>
#include<array>
using namespace std;
const int MAX_N=1e3+5;
int dp[MAX_N][MAX_N];
bool swaps[MAX_N][MAX_N][2];
int n;
int a[MAX_N];
vector<int>g[MAX_N];
int rec(int u,int idx)
{
    if(dp[u][idx]!=0)return dp[u][idx];

    int x[3];
    int sz=0;
    x[sz++]=a[idx];
    for(int v:g[u])
    {
        x[sz++]=a[v];
    }
    int mipos=0;
    int mi=x[0];
    for(int i=1;i<sz;i++)
    {
        if(x[i]<x[mipos])
        {
            mipos=i;
            mi=x[i];
        }
    }

    dp[u][idx]=mi;

    if(mipos==0)
    {
        for(int v:g[u])
        {
            rec(v,v);
        }
    }
    else if(mipos==1)
    {
        swaps[u][idx][0]=1;
        for(int v:g[u])
        {
            if(a[v]==x[1])rec(v,idx);
            else rec(v,v);
        }
    }
    else
    {
        swaps[u][idx][1]=1;
        int l=g[u][0];
        int r=g[u][1];
        if(rec(l,idx)<rec(l,l))
        {
            swaps[u][idx][0]=1;
            rec(r,l);
        }
        else if(rec(l,idx)==rec(l,l))
        {
            if(rec(r,l)<rec(r,idx))swaps[u][idx][0]=1;
        }
        else rec(r,idx);
    }

    return dp[u][idx];
}
void path(int u,int idx)
{
    int l,r;
    int c=idx;
    if(g[u].size())l=g[u][0];
    if(g[u].size()>1)r=g[u][1];

    if(swaps[u][idx][0]){swap(a[u],a[g[u][0]]);swap(c,l);}
    if(swaps[u][idx][1]){swap(a[u],a[g[u][1]]);swap(c,r);}

    if(g[u].size())path(g[u][0],l);
    if(g[u].size()>1)path(g[u][1],r);
}
signed main ()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        if(i*2<=n)g[i].push_back(i*2);
        if(i*2+1<=n)g[i].push_back(i*2+1);
    }
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    rec(1,1);
    path(1,1);
    for(int i=1;i<=n;i++)
    {
        cout<<a[i]<<" ";
    }
    cout<<"\n";
    return 0;
}

Compilation message (stderr)

swap.cpp: In function 'void path(int, int)':
swap.cpp:89:23: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
   89 |     if(swaps[u][idx][1]){swap(a[u],a[g[u][1]]);swap(c,r);}
      |        ~~~~~~~~~~~~~~~^
swap.cpp:91:24: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]
   91 |     if(g[u].size())path(g[u][0],l);
      |                    ~~~~^~~~~~~~~~~

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