# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
551542 | krit3379 | 철로 (IOI14_rail) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define N 5005
struct A{
int x,id;
bool operator<(const A& o)const{
return x<o.x;
}
};
A l,r;
vector<A> v;
map<int,int> mp;
void findLocation(int n, int first, int location[], int stype[]){
int i,pos;
location[0]=first;
stype[0]=1;
if(n==1)return ;
l={first,0};
mp[l.x]=1;
for(i=1;i<n;i++)v.push_back({getDistance(0,i),i});
sort(v.begin(),v.end());
r={l.x+v[0].x,v[0].id};
location[v[0].id]=r.x;
stype[v[0].id]=2;
mp[r.x]=2;
for(i=1;i<v.size();i++){
int xl,xr;
xl=getDistance(v[i].id,l.id);
xr=getDistance(v[i].id,r.id);
pos=l.x+xl;
int val=(pos+r.x-xr)/2;
if((mp.count(val)&&mp[val]==1)||(!mp.count(val)&&val>first)){
A temp={pos,v[i].id};
location[v[i].id]=pos;
stype[v[i].id]=2;
r=max(r,temp);
mp[pos]=2;
continue;
}
pos=r.x-xr;
A temp={pos,v[i].id};
location[v[i].id]=pos;
stype[v[i].id]=1;
l=min(l,temp);
mp[pos]=1;
}
return ;
}