| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 573185 |
2022-06-06T08:34:11 Z |
fdnfksd |
Swap (BOI16_swap) |
C++17 |
|
10 ms |
14424 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]);
| ^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
14424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
14424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
14424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
14424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
14424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
