#include "rail.h"
#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;
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);
auto [add, fs] = dis[1];
int l = 0, r = fs;
loc[fs] = first+add;
stype[fs] = 2;
set<int> lc = {loc[0]}, rd = {loc[fs]};
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);
// assert(df <= loc[fs]-loc[l] + dl);
int dif = (loc[fs]-loc[l] + dl - df)/2;
if(lc.count(loc[l]+dif)){
//it's l )
loc[i] = loc[l]+dl;
stype[i] = 2;
}
else{
loc[i] = loc[fs]-df;
stype[i] = 1;
l = i;
lc.insert(loc[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);
int dif = (loc[r]-loc[0] + dr - d0)/2;
if(rd.count(loc[r]-dif)){
// 0 1 ( r
loc[i] = loc[r]-dr;
stype[i] = 1;
}
else{
loc[i] = loc[0]+d0;
stype[i] = 2;
r = i;
rd.insert(loc[i]);
}
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
86 ms |
620 KB |
Output is correct |
2 |
Correct |
85 ms |
620 KB |
Output is correct |
3 |
Correct |
95 ms |
620 KB |
Output is correct |
4 |
Correct |
86 ms |
620 KB |
Output is correct |
5 |
Correct |
86 ms |
620 KB |
Output is correct |
6 |
Correct |
85 ms |
620 KB |
Output is correct |
7 |
Correct |
86 ms |
620 KB |
Output is correct |
8 |
Correct |
85 ms |
620 KB |
Output is correct |
9 |
Correct |
83 ms |
620 KB |
Output is correct |
10 |
Correct |
84 ms |
620 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
85 ms |
620 KB |
Output is correct |
2 |
Correct |
86 ms |
620 KB |
Output is correct |
3 |
Correct |
85 ms |
620 KB |
Output is correct |
4 |
Correct |
83 ms |
620 KB |
Output is correct |
5 |
Correct |
84 ms |
620 KB |
Output is correct |
6 |
Correct |
98 ms |
620 KB |
Output is correct |
7 |
Correct |
88 ms |
620 KB |
Output is correct |
8 |
Correct |
84 ms |
620 KB |
Output is correct |
9 |
Correct |
84 ms |
620 KB |
Output is correct |
10 |
Correct |
84 ms |
652 KB |
Output is correct |
11 |
Correct |
84 ms |
620 KB |
Output is correct |
12 |
Correct |
83 ms |
620 KB |
Output is correct |
13 |
Correct |
83 ms |
620 KB |
Output is correct |
14 |
Correct |
85 ms |
620 KB |
Output is correct |
15 |
Correct |
83 ms |
620 KB |
Output is correct |
16 |
Correct |
97 ms |
620 KB |
Output is correct |
17 |
Correct |
95 ms |
620 KB |
Output is correct |
18 |
Correct |
83 ms |
620 KB |
Output is correct |
19 |
Correct |
84 ms |
620 KB |
Output is correct |
20 |
Correct |
83 ms |
620 KB |
Output is correct |