oj.uz

Submission #573198

# Submission time Handle Problem Language Result Execution time Memory
573198 2022-06-06T08:48:52 Z fdnfksd Swap (BOI16_swap) C++14
100 / 100
 86 ms 37196 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]=i;
    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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14420 KB Output is correct
2 Correct 9 ms 14428 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 7 ms 14416 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14420 KB Output is correct
2 Correct 9 ms 14428 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 7 ms 14416 KB Output is correct
6 Correct 8 ms 14420 KB Output is correct
7 Correct 7 ms 14420 KB Output is correct
8 Correct 8 ms 14420 KB Output is correct
9 Correct 8 ms 14380 KB Output is correct
10 Correct 7 ms 14420 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14420 KB Output is correct
2 Correct 9 ms 14428 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 7 ms 14416 KB Output is correct
6 Correct 8 ms 14420 KB Output is correct
7 Correct 7 ms 14420 KB Output is correct
8 Correct 8 ms 14420 KB Output is correct
9 Correct 8 ms 14380 KB Output is correct
10 Correct 7 ms 14420 KB Output is correct
11 Correct 7 ms 14420 KB Output is correct
12 Correct 8 ms 14420 KB Output is correct
13 Correct 7 ms 14420 KB Output is correct
14 Correct 8 ms 14424 KB Output is correct
15 Correct 8 ms 14520 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14420 KB Output is correct
2 Correct 9 ms 14428 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 7 ms 14416 KB Output is correct
6 Correct 8 ms 14420 KB Output is correct
7 Correct 7 ms 14420 KB Output is correct
8 Correct 8 ms 14420 KB Output is correct
9 Correct 8 ms 14380 KB Output is correct
10 Correct 7 ms 14420 KB Output is correct
11 Correct 7 ms 14420 KB Output is correct
12 Correct 8 ms 14420 KB Output is correct
13 Correct 7 ms 14420 KB Output is correct
14 Correct 8 ms 14424 KB Output is correct
15 Correct 8 ms 14520 KB Output is correct
16 Correct 19 ms 17116 KB Output is correct
17 Correct 20 ms 17108 KB Output is correct
18 Correct 20 ms 17108 KB Output is correct
19 Correct 26 ms 19960 KB Output is correct
20 Correct 28 ms 19916 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14420 KB Output is correct
2 Correct 9 ms 14428 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 7 ms 14416 KB Output is correct
6 Correct 8 ms 14420 KB Output is correct
7 Correct 7 ms 14420 KB Output is correct
8 Correct 8 ms 14420 KB Output is correct
9 Correct 8 ms 14380 KB Output is correct
10 Correct 7 ms 14420 KB Output is correct
11 Correct 7 ms 14420 KB Output is correct
12 Correct 8 ms 14420 KB Output is correct
13 Correct 7 ms 14420 KB Output is correct
14 Correct 8 ms 14424 KB Output is correct
15 Correct 8 ms 14520 KB Output is correct
16 Correct 19 ms 17116 KB Output is correct
17 Correct 20 ms 17108 KB Output is correct
18 Correct 20 ms 17108 KB Output is correct
19 Correct 26 ms 19960 KB Output is correct
20 Correct 28 ms 19916 KB Output is correct
21 Correct 55 ms 25460 KB Output is correct
22 Correct 60 ms 25532 KB Output is correct
23 Correct 53 ms 25492 KB Output is correct
24 Correct 86 ms 37196 KB Output is correct
25 Correct 83 ms 37152 KB Output is correct