| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 142886 | babo | 커다란 상품 (IOI17_prize) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define inf 1000000000000000000ll
#define all(x) (x).begin(),(x).end()
#define ab(x) ((x)>0?(x):-(x))
#define L long long
using namespace std;
L n;
L chk[1000010];
struct S{
L s,e;
};
vector<S>v;
vector<L>w;
L minimum_walk(vector<int>p,int s){
L i,ret=0,cntgroup=-1,startdist=inf;
n=p.size();
for(i=0;i<n;i++)
if(p[i]!=i)
w.push_back(i);
vector<L>::iterator it=lower_bound(all(w),s+1);
if(it!=w.end())
startdist=min(startdist,*it-s);
it=upper_bound(all(w),s);
if(it!=w.end())
startdist=min(startdist,(*prev(it))-s);
for(i=0;i<n;i++)
{
if(p[i]==i) p[i]=-1;
}
for(i=0;i<n;i++)
{
if(p[i]==-1) continue;
if(!chk[i])
{
L s=i,e=i;
L temp=p[i];
ret+=ab(p[i]-i);
chk[temp]=1;
while(temp!=i)
{
e=max(e,temp);
ret+=ab(p[temp]-temp);
temp=p[temp];
chk[temp]=1;
}
v.push_back((S){s,e});
}
}
sort(all(v),[](S a,S b){
return a.s<b.s;
});
L emax=-1;
for(i=0;i<v.size();i++)
{
//printf("s e %lld %lld\n",v[i].s,v[i].e);
if(v[i].s>emax) cntgroup++;
emax=max(emax,v[i].e);
}
//printf("%lld %lld %lld\n",ret,cntgroup,startdist);
return ret+cntgroup*2+startdist*2;
}