oj.uz

Submission #573196

# Submission time Handle Problem Language Result Execution time Memory
573196 2022-06-06T08:46:37 Z fdnfksd Swap (BOI16_swap) C++17
0 / 100
 7 ms 14292 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma,popcnt")
#define pli pair<long long,long long>
#define pb push_back
const long long INF=-1e18;
using namespace std;
using ll =long long ;
const ll maxN=3e5+1;
ll n, a[maxN];
map<int,int>pos[maxN];
ll final_pos(ll i, ll val)
{
    if(i*2>n) return pos[i][val]=i;
    if(pos[i][val]>0) return pos[i][val];
    ll mn=min(a[i*2],a[i*2+1]);
    if(mn>=val) return pos[i][val]=val;
    else
    {
        if(mn==a[i*2])
        {
            return pos[i][val]=final_pos(i*2,val);
        }
        else
        {
            ll mx_child=max(val,a[i*2]);
            ll mn_child=min(val,a[i*2]);
            ll left=final_pos(i*2,mn_child);
            ll right=final_pos(i*2+1,mn_child);
            if(left<right)
            {
                // con trai nhan gia tri min
                if(mn_child==val) pos[i][val]=final_pos(i*2,val);
                else pos[i][val]=final_pos(i*2+1,val);
            }
            else
            {
                if(mn_child==val) pos[i][val]=final_pos(i*2+1,val);
                else pos[i][val]=final_pos(i*2,val);
            }
        }
    }
    return pos[i][val];
}
void solve()
{
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i];
    a[n+1]=1e10;
    for(int i=1;i<=n;i++)
    {
        if(i*2>n) continue;
        ll mn=min(a[i*2],a[i*2+1]);
        if(mn>=a[i]) continue;
        else
        {
            if(mn==a[i*2]) swap(a[i],a[i*2]);
            else
            {
                swap(a[i],a[i*2+1]);
                ll mn_child=min(a[i*2+1],a[i*2]);
                ll mx_child=max(a[i*2+1],a[i*2]);
                ll left=final_pos(i*2,mn_child);
                ll right=final_pos(i*2+1,mn_child);
                if(left<right)
                {
                    a[i*2]=mn_child;
                    a[i*2+1]=mx_child;
                }
                else
                {
                    a[i*2]=mx_child;
                    a[i*2+1]=mn_child;
                }
            }
        }
    }
    for(int i=1;i<=n;i++) cout << a[i]<<' ';
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	solve();
}

Compilation message

swap.cpp: In function 'll final_pos(ll, ll)':
swap.cpp:27:16: warning: unused variable 'mx_child' [-Wunused-variable]
   27 |             ll mx_child=max(val,a[i*2]);
      |                ^~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 27.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 32.0

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