#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
//#define endl "\n"
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
const ll maxn=4e5+10;
const ll mod=1e9+7 ;
const ll base=2e9;
/// i believe myself
/// goal 2/7
ll a[maxn];
ll b[maxn];
ll valnw[maxn];
ll pos[maxn];
ll n;
pll par[maxn];
ll valpre[maxn];
ll st[maxn];
void dfs(ll u,ll x)
{
a[u]=b[u];
if (x)
par[u]=make_pair(b[u],u);
if (u*2<=n)
dfs(u*2,1);
if (u*2+1<=n)
dfs(u*2+1,1);
}
pll pt(pll p,ll u)
{
if (p.ss==u)
return make_pair(base,-1);
else
return p;
}
void dfs1(ll u,ll mx)
{
if (u>mx)
return ;
if (st[u]==0)
{
}
else if (st[u]==1)
{
swap(a[u],a[u*2]);
if (par[u].ss!=u)
par[u*2]=par[u];
}
else if (st[u]==2)
{
swap(a[u],a[u*2+1]);
ll h=min(a[u*2],a[u*2+1]);
par[u*2]=min(make_pair(h,u),pt(par[u],u));
par[u*2+1]=min(make_pair(h,u),pt(par[u],u));
}
else
{
swap(a[u],a[u*2+1]);
if (st[u]==3)
swap(a[u*2],a[u*2+1]);
par[u*2]=min(pt(par[u],u),make_pair(a[u*2],u*2));
par[u*2+1]=min(pt(par[u],u),make_pair(a[u*2+1],u*2+1));
}
dfs1(u*2,mx);
dfs1(u*2+1,mx);
}
pll vals[maxn];
void dosth(ll x,ll y)
{
swap(a[x],a[y]);
swap(pos[a[x]],pos[a[y]]);
}
void update(ll x,ll y,ll p)
{
swap(vals[p].ff,vals[p].ss);
dosth(x,y);
ll nw=x;
do
{
nw/=2;
if (nw==p) break;
if (vals[nw].ff==vals[p].ss)
{
vals[nw].ff=vals[p].ff;
}
else
{
vals[nw].ss=vals[p].ff;
}
}
while (nw!=p);
nw=y;
do
{
nw/=2;
if (nw==p) break;
if (vals[nw].ff==vals[p].ff)
{
vals[nw].ff=vals[p].ss;
}
else
{
vals[nw].ss=vals[p].ss;
}
}
while (nw!=p);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
if (fopen("t.inp","r"))
{
freopen("test.inp","r",stdin);
freopen("test.out","w",stdout);
}
cin>> n;
for (int i=1; i<=n; i++)
{
cin>> a[i];
b[i]=a[i];
pos[a[i]]=i;
par[i]=make_pair(a[i],i);
// keep this value
}
for (ll i=1; i<=n; i++)
{
pll val=make_pair(base,-1);
if (i*2<=n)
val=min(val,make_pair(a[i*2],(ll)i*2));
if (i*2+1<=n)
val=min(val,make_pair(a[i*2+1],(ll)i*2+1));
ll nw=i/2;
pll val1=make_pair(a[i],i);
while (nw)
{
if (st[nw]==2&&a[i]==max(vals[nw].ff,vals[nw].ss)&&pos[max(vals[nw].ff,vals[nw].ss)]<pos[min(vals[nw].ff,vals[nw].ss)])
val1=min(val1,make_pair(min(vals[nw].ff,vals[nw].ss),nw));
nw/=2;
}
// cout <<i<<" wtf"<<endl;
if (val.ff>val1.ff)
{
st[i]=0;
if (val1.ss!=i)
{
ll nw=i;
vector<ll> vt;
vt.pb(nw);
while (1)
{
ll h=nw/2;
vt.pb(h);
if (h==val1.ss)
break;
else
nw=h;
}
reverse(vt.begin(),vt.end());
ll t=(vals[val1.ss].ss==val1.ff);
ll t1=(vt[1]==(val1.ss*2+1));
ll p=val1.ss;
if ((t^t1)==0)
st[val1.ss]=4;
else
{
update(pos[vals[val1.ss].ff],pos[vals[val1.ss].ss],p);
st[val1.ss]=3;
}
for (int i=1; i+1<vt.size(); i++)
{
ll x=vt[i];
if (st[x]==2)
{
st[x]=(3+(vt[i+1]%2));
if (st[x]==3)
{
update(pos[vals[x].ff],pos[vals[x].ss],p);
}
}
}
}
}
else
{
if (val.ss==i*2)
{
st[i]=1;
dosth(i,i*2);
}
else
{
st[i]=2;
valpre[i]=a[i];
dosth(i,i*2+1);
vals[i]=make_pair(a[i*2],a[i*2+1]);
}
}
if (i==0)
{
cout <<i<<" wtf"<<endl;
cout <<val.ff<<" "<<val.ss<<" "<<val1.ff<<" "<<val1.ss<<" chk1"<<endl;
for (int i=1;i<=n;i++)
{
cout <<a[i]<<" "<<vals[i].ff<<" "<<vals[i].ss<<" "<<st[i]<<endl;
}
cout <<endl;
// cout <<t<<" "<<t1<<" "<<val1.ss<<endl;
// if (i==6) return 0;
}
/*for (int i=1;i<=n;i++)
{
cout <<a[i]<<" ";
}
cout <<endl;*/
}
for (int i=1; i<=n; i++)
{
cout <<a[i]<<" ";
}
}
Compilation message
swap.cpp: In function 'int main()':
swap.cpp:190:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
190 | for (int i=1; i+1<vt.size(); i++)
| ~~~^~~~~~~~~~
swap.cpp:130:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
130 | freopen("test.inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
swap.cpp:131:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
131 | freopen("test.out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
