| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1279233 | MMihalev | Ancient Books (IOI17_books) | C++20 | 0 ms | 0 KiB |
#include<iostream>
#include<vector>
//#include "books.h"
using namespace std;
const int MAX_N=1e6+6;
int col[MAX_N];
int cols;
int a[MAX_N];
int l[MAX_N];
int r[MAX_N];
int n;
long long ans;
pair<int,int>findcomponent(int id)
{
int ll=id,rr=id;
int oldl=ll+1,oldr=rr-1;
while(1)
{
int nl=ll,nr=rr;
for(int i=ll;i<oldl;i++)
{
if(col[i]==0)continue;
nl=min(nl,l[col[i]]);
nr=max(nr,r[col[i]]);
}
for(int i=oldr+1;i<=rr;i++)
{
if(col[i]==0)continue;
nl=min(nl,l[col[i]]);
nr=max(nr,r[col[i]]);
}
if(nl==ll && nr==rr)break;
oldl=ll;oldr=rr;
ll=nl;rr=nr;
}
return {ll,rr};
}
long long minimum_walk(std::vector<int> p, int s)
{
n=p.size();
s++;
for(int i=1;i<=n;i++)
{
l[i]=1e9;
r[i]=-1;
a[i]=p[i-1]+1;
}
///init stuff
for(int i=1;i<=n;i++)
{
ans+=abs(i-a[i]);
if(col[i]==0)
{
if(i!=s && i==a[i])continue;
cols++;
int pos=i;
while(col[pos]==0)
{
l[cols]=min(l[cols],pos);
r[cols]=max(r[cols],pos);
col[pos]=cols;
pos=a[pos];
}
}
}
int tmpstart=-1,tmpend=-1;
int compstart=-1,compend=-1;
vector<int>sep;
bool has=0;
int active=0;
int e=n;
while(col[e]==0)e--;
for(int i=1;i<=e;i++)
{
if(has && active==0)
{
sep.push_back(i-1);
}
int curcol=col[i];
if(l[curcol]==i)
{
if(active==0)tmpstart=i;
has=1;
active++;
}
if(r[curcol]==i)
{
if(active==1)
{
tmpend=i;
}
active--;
}
if(tmpstart<=s && s<=tmpend)
{
compstart=tmpstart;
compend=tmpend;
}
}
int ll=s,rr=s;
tie(ll,rr)=findcomponent(s);
while(1)
{
if(ll==compstart && rr==compend)break;
int distr=0,tmpr=rr;
while(1)
{
distr++;
tmpr++;
while(col[tmpr]==0)
{
distr++;
tmpr++;
}
bool foundnew=0;
int newcomponentl,newcomponentr;
tie(newcomponentl,newcomponentr)=findcomponent(tmpr);
if(newcomponentl<ll)
{
ll=componentl;
rr=componentr;
foundnew=1;
}
else
{
tmpr=newcomponentr;
}
if(foundnew)
{
break;
}
}
int distl=0,tmpl=ll;
while(1)
{
distl++;
tmpl--;
while(col[tmpl]==0)
{
distl++;
tmpl--;
}
bool foundnew=0;
int newcomponentl,newcomponentr;
tie(newcomponentl,newcomponentr)=findcomponent(tmpl);
if(newcomponentr>rr)
{
ll=newcomponentl;
rr=newcomponentr;
foundnew=1;
}
else
{
tmpl=newcomponentl;
}
if(foundnew)break;
}
ans+=2*min(distl,distr);
}
if(sep.size()==0)return ans;
///cycle stuff
for(int i=sep.size()-1;i>=0;i--)
{
if(sep[i]>=s)ans+=2;
}
///right part
for(int i=0;i<sep.size();i++)
{
if(sep[i]<s)ans+=2;
}
///left part
return ans;
}