| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 260051 | arnold518 | Swap (BOI16_swap) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 2e5;
int N, A[MAXN+10];
vector<int> V[MAXN+10];
unordered_map<int, vector<bool>> vis[MAXN+10];
unordered_map<int, vector<int>> dp[MAXN+10];
vector<int> &solve(int now, int pp)
{
int qq=lower_bound(V[now].begin(), V[now].end(), pp)-V[now].begin();
if(V[now][qq]!=pp) while(1);
if(vis[now][qq]) return dp[now][qq];
vis[now][qq]=1;
vector<int> &ret=dp[now][qq];
if(now*2>N)
{
ret.push_back(A[pp]);
return ret;
}
if(now*2+1>N)
{
if(A[pp]>A[now*2])
{
ret.push_back(A[now*2]);
ret.push_back(A[pp]);
}
else
{
ret.push_back(A[pp]);
ret.push_back(A[now*2]);
}
return ret;
}
if(A[pp]<A[now*2] && A[pp]<A[now*2+1])
{
vector<int> &p=solve(now*2, now*2), &q=solve(now*2+1, now*2+1);
ret.push_back(A[pp]);
for(int k=0, i=0, j=0; i<p.size() || j<q.size(); k++)
{
for(int t=0; t<(1<<k) && i<p.size(); t++, i++) ret.push_back(p[i]);
for(int t=0; t<(1<<k) && j<q.size(); t++, j++) ret.push_back(q[j]);
}
return ret;
}
if(A[now*2]<A[pp] && A[now*2]<A[now*2+1])
{
vector<int> &p=solve(now*2, pp), &q=solve(now*2+1, now*2+1);
ret.push_back(A[now*2]);
for(int k=0, i=0, j=0; i<p.size() || j<q.size(); k++)
{
for(int t=0; t<(1<<k) && i<p.size(); t++, i++) ret.push_back(p[i]);
for(int t=0; t<(1<<k) && j<q.size(); t++, j++) ret.push_back(q[j]);
}
return ret;
}
if(A[now*2+1]<A[pp] && A[now*2+1]<A[now*2])
{
vector<int> &p1=solve(now*2, pp), &q1=solve(now*2+1, now*2);
vector<int> &p2=solve(now*2, now*2), &q2=solve(now*2+1, pp);
ret.push_back(A[now*2+1]);
int flag=0;
for(int k=0, i=0, j=0; i<p1.size() || j<q1.size(); k++)
{
for(int t=0; t<(1<<k) && i<p1.size(); t++, i++)
{
if(flag==1) ret.push_back(p1[i]);
if(flag==2) ret.push_back(p2[i]);
if(flag==0)
{
if(p1[i]==p2[i]) ret.push_back(p1[i]), flag=0;
if(p1[i]<p2[i]) ret.push_back(p1[i]), flag=1;
if(p1[i]>p2[i]) ret.push_back(p2[i]), flag=2;
}
}
for(int t=0; t<(1<<k) && j<q1.size(); t++, j++)
{
if(flag==1) ret.push_back(q1[j]);
if(flag==2) ret.push_back(q2[j]);
if(flag==0)
{
if(q1[j]==q2[j]) ret.push_back(q1[j]), flag=0;
if(q1[j]<q2[j]) ret.push_back(q1[j]), flag=1;
if(q1[j]>q2[j]) ret.push_back(q2[j]), flag=2;
}
}
}
return ret;
}
}
int main()
{
scanf("%d", &N);
for(int i=1; i<=N; i++) scanf("%d", &A[i]);
for(int i=1; i<=N; i++)
{
int now=i;
while(now!=1)
{
V[i].push_back(now);
if(now%2) V[i].push_back(now-1);
now/=2;
}
V[i].push_back(1);
reverse(V[i].begin(), V[i].end());
//vis[i].resize(V[i].size());
//dp[i].resize(V[i].size());
}
vector<int> ans=solve(1, 1);
for(auto it : ans) printf("%d ", it);
}