| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 121176 | Rudy420 | Rail (IOI14_rail) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define ll long long
#define pi pair<int,int>
#define pl pair<ll,ll>
#define pd pair<double,double>
#define ld long double
#define pld pair<ld,ld>
#define lg length()
#define sz size()
#define vi vector<int>
#define vl vector<ll>
#define vp vector<pi>
#define vpl vector<pl>
#define pb push_back
#define INF 1000000005
#define LINF 1000000000000000005
#ifdef LOCAL_DEFINE
mt19937 rng(69);
#else
seed_seq seq{
(uint64_t) chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count(),
//(uint64_t) __builtin_ia32_rdtsc(),
//(uint64_t) (uintptr_t) make_unique<char>().get()
};
mt19937 rng(seq);
#endif
//#include "rail.h"
void findLocation(int n, int x, int p[], int t[])
{
if(n==1){
p[0]=x; t[0]=1;
return;
}
if(n==2){
p[0]=x;
p[1]=x+getDistance(0,1);
t[0]=1;
t[1]=2;
return;
}
int a[n+5],b[n+5];
for(int i=1;i<n;i++) a[i]=getDistance(0,i);
int mn=INF,y=-1;
for(int i=1;i<n;i++){
if(a[i]<mn) mn=a[i],y=i;
}
for(int i=1;i<n;i++){
if(i==y) continue;
b[i]=getDistance(y,i);
}
mn=INF;
int z=-1;
for(int i=1;i<n;i++){
if(b[i]<mn) mn=b[i],z=i;
}
int diff=b[z]-a[y];
p[z]=x-diff;
p[y]=p[z]+b[z];
t[z]=1;
t[y]=2;
for(int i=0;i<n;i++){
a[i]+=diff;
}
vector <pi> l,r;
vector <int> u,v;
for(int i=0;i<n;i++){
if(i==y || i==z) continue;
if(a[i]>b[i]) l.pb({b[i],i});
else r.pb({a[i],i});
}
sort(l.begin(),l.end());
u.pb(p[z]);
int f=z;
for(pi i : l){
int d=getDistance(i.y,f);
p[i.y]=p[f]+d;
if(p[i.y]>p[z]){
p[i.y]=p[y]-b[i.y];
t[i.y]=1;
u.pb(p[i.y]);
}
int c=*(--upper_bound(u.begin(),u.end(),p[i.y],greater<int>()));
if(b[i.y]==p[i.y]+p[y]-2*c){
t[i.y]=2;
}
else{
p[i.y]=p[y]-b[i.y];
t[i.y]=1;
u.pb(p[i.y]);
}
}
sort(r.begin(),r.end());
v.pb(p[y]);
f=y;
for(pi i : r){
int d=getDistance(i.y,f);
p[i.y]=p[f]-d;
if(p[i.y]<p[y]){
p[i.y]=p[y]+a[i.y];
t[i.y]=2;
v.pb(p[i.y]);
}
int c=*(upper_bound(v.begin(),v.end(),p[i.y]));
if(a[i.y]==2*c-p[i.y]-p[y]){
t[i.y]=1;
}
else{
p[i.y]=p[y]+a[i.y];
t[i.y]=2;
v.pb(p[i.y]);
}
}
}