| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 563614 |
2022-05-17T17:34:15 Z |
Dymo |
Swap (BOI16_swap) |
C++14 |
|
1000 ms |
340 KB |
#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 (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 (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("test.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) val1=min(val1,make_pair(min(vals[nw].ff,vals[nw].ss),nw));
nw/=2;
}
//if (i==4) cout <<val.ff<<" "<<val.ss<<" "<<val1.ff<<" "<<val1.ss<<" chk1"<<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));
if ((t^t1)==0)
st[val1.ss]=4;
else
{
st[val1.ss]=3;
}
//if (i==4) cout <<t<<" "<<t1<<" chkwtf"<<endl;
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 (i==4)
{
for (auto to:vt) cout <<to<<" "<<st[to]<<" chk4"<<endl;
}*/
ll p=val1.ss;
for (int i=0;i+1<vt.size();i++)
{
if (st[vt[i]]==3)
{
ll x=pos[vals[vt[i]].ff];
ll y=pos[vals[vt[i]].ss];
update(x,y,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]);
}
}
/*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:181:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
181 | for (int i=1; i+1<vt.size(); i++)
| ~~~^~~~~~~~~~
swap.cpp:194:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
194 | for (int i=0;i+1<vt.size();i++)
| ~~~^~~~~~~~~~
swap.cpp:126:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
126 | freopen("test.inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
swap.cpp:127:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
127 | freopen("test.out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1090 ms |
340 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1090 ms |
340 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1090 ms |
340 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1090 ms |
340 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1090 ms |
340 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
