oj.uz

Submission #1029631

# Submission time Handle Problem Language Result Execution time Memory
1029631 2024-07-21T06:42:27 Z MMihalev Swap (BOI16_swap) C++14
0 / 100
 0 ms 348 KB 
#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];
        if(rec(l,idx)<rec(l,l))
        {
            swaps[u][idx][0]=1;
        }
    }
    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[idx],a[g[u][0]]);swap(c,l);}
    if(swaps[u][idx][1]){swap(a[idx],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

swap.cpp: In function 'void path(int, int)':
swap.cpp:81:24: warning: 'idx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   81 |     if(g[u].size())path(g[u][0],l);
      |                    ~~~~^~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -