| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 376993 | crackersamdjam | 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>
#define all(x) (x).begin(), (x).end()
#ifndef ONLINE_JUDGE
template<typename T>
void pr(T a){std::cerr<<a<<std::endl;}
template<typename T,typename... Args>
void pr(T a, Args... args) {std::cerr<<a<<' ',pr(args...);}
#else
template<typename... Args>
void pr(Args... args){}
#endif
using namespace std;
#ifdef LOCAL
int nn = 4, ss[] = {2, 5, 3, 1}, tt[] = {1, 0, 1, 1};
int dd[4][4] = {{0, 3, 5, 7}, {3, 0, 2, 4}, {5, 0, 2, 6}, {7, 4, 6, 0}};
int getDistance(int i, int j){
assert(0 <= i and i < nn);
assert(0 <= j and j < nn);
return dd[i][j];
}
#endif
void findLocation(int n, int first, int loc[], int stype[]){
array<int, 2> dis[n];
dis[0] = {0, 0};
loc[0] = first;
stype[0] = 1;
for(int i = 1; i < n; i++){
dis[i] = {getDistance(0, i), i};
}
sort(dis, dis+n);
int l = 0, r = dis[1][1];
loc[r] = first+dis[1][0];
stype[r] = 2;
auto [add, fs] = dis[1];
for(int j = 2; j < n; j++){
auto [d0, i] = dis[j];
int df = getDistance(fs, i);
if(d0+add == df){
//then 0->i turns at fs
// 0 ( 1
// ( l 0 1
// l ) 0 1
if(df < add){
// first case
loc[i] = loc[fs]-df;
stype[i] = 1;
continue;
}
// now check it's distance from l to know which case (out of last two)
int dl = getDistance(l, i);
if(df == loc[fs]-loc[l] + dl){
//it's l )
loc[i] = loc[l]+dl;
stype[i] = 2;
}
else{
loc[i] = loc[fs]-df;
stype[i] = 1;
l = i;
}
}
else{
//it doesn't turn at fs
// 0 1 ( r
// 0 1 r )
int dr = getDistance(r, i);
// assert(d0 >= loc[r]-loc[0] + dr);
if(d0 == loc[r]-loc[0] + dr){
// 0 1 ( r
loc[i] = loc[r]-dr;
stype[i] = 1;
}
else{
loc[i] = loc[0]+d0;
stype[i] = 2;
r = i;
}
}
// dif = (d0 - (loc[r]-loc[0]) - dr)
// if dif > 0, then it's somewhere on right
// but if on right and dif = 0,
// that means that d0 = dr + (loc[r]-loc[0])
// let m be the point where r->i turns right
// 0->m + m->r + r->i = dr + 0->m + m->r
// r->i = dr
// r->i = m<-r + m->r + r->i
// m->r = 0]
// so impossible
}
}
/*
get all from station 0 and sort by distance
the first one is the first D right of 0
then loop through stations in sorted order,
compare dis(0, i) and dis(1st D, i) to see if on left or right side
then, to know if it's ( or ), query from most leftmost/rightmost existing one
*/
#ifdef LOCAL
int main(){
int n = 4, first = 2, locations[n], stype[n];
findLocation(n, first, locations, stype);
for(int i = 0; i < n; i++)
cout<<locations[i]<<' ';
cout<<'\n';
for(int i = 0; i < n; i++)
cout<<stype[i]<<' ';
cout<<'\n';
}
#endif