# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
122483 | someone_aa | 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 "rail.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 5100;
ll d0[maxn], n;
ll dx[maxn];
map<int,bool> exist_right;
map<int,bool> exist_left;
void findLocation(int N, int first, int location[], int stype[])
{
n = N;
location[0] = first;
stype[0] = 1;
ll minval = LLONG_MAX;
ll x = -1;
for(int i=1;i<n;i++) {
d0[i] = getDistance(0, i);
if(d0[i] < minval) {
minval = d0[i];
x = i;
}
}
for(int i=1;i<n;i++) {
if(i == x) continue;
dx[i] = getDistance(i, x);
}
location[x] = first + d0[x];
stype[x] = 2;
exist_left[location[x]] = true;
vector<pair<ll, ll> > lft, rght;
for(int i=1;i<n;i++) {
if(i == x) continue;
if(d0[x] + dx[i] == d0[x]) {
lft.pb(mp(dx[i], i));
}
else {
rght.pb(mp(d0[i], i));
}
}
/*cout<<x<<"\n";
cout<<"on left: \n";
for(auto i:lft) {
cout<<i.first<<" "<<i.second<<"\n";
}
cout<<"and on right\n";
for(auto i:rght) {
cout<<i.first<<" "<<i.second<<"\n";
}*/
sort(lft.begin(), lft.end());
sort(rght.begin(), rght.end());
if(rght.size() > 0) {
int ind = rght[0].second;
int dst = d0[ind];
stype[ind] = 2;
location[ind] = location[0] + dst;
exist_right[location[ind]] = true;
int ind_limit = ind;
for(int i=1;i<rght.size();i++) {
ind = rght[i].second;
dst = d0[ind];
int temp = getDistance(ind_limit, ind);
ll z = abs(d0[ind] - d0[ind_limit] - temp);
z /= 2;
if(exist_right[location[ind_limit] - z]) {
// TYPE C
location[ind] = location[ind_limit] - temp;
stype[ind] = 1;
}
else {
// TYPE D
location[ind] = location[0] + d0[ind];
exist_right[location[ind]] = true;
stype[ind] = 2;
ind_limit = ind;
}
}
}
if(lft.size() > 0) {
int ind = lft[0].second;
int dst = lft[0].first;
stype[ind] = 1;
location[ind] = location[x] - dst;
exist_left[location[ind]] = true;
int ind_limit = ind;
for(int i=1;i<lft.size();i++) {
ind = lft[i].second;
dst = lft[i].first;
ll temp = getDistance(ind_limit, ind);
ll z = abs(dx[ind] - dx[ind_limit] - temp);
z /= 2;
if(exist_left[location[ind_limit] + z]) {
// TYPE D
stype[ind] = 2;
location[ind] = location[ind_limit] + temp;
}
else {
// TYPE C
stype[ind] = 1;
location[ind] = location[x] - dx[ind];
ind_limit = ind;
exist_left[location[ind]] = true;
}
}
}
return location[x];
}