#include "rail.h"
#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
using namespace std;
using pii = pair<int, int>;
int n, l, r, tt[1000000];
vector<pii> vec;
void findLocation(int N, int first, int location[], int stype[])
{
memset(tt,-1,sizeof tt);
n = N;
l = 0;
location[0] = first;
stype[0] = 1;
for(int i = 1; i < n; i++){
vec.pb({getDistance(0, i), i});
}
sort(vec.begin(), vec.end());
if(n == 1) return;
r = vec[0].S;
location[r] = location[l] + vec[0].F;
tt[location[r]] = 1;
stype[r] = 2;
for(int i = 1; i < n - 1; i++){
int k = vec[i].S;
int x = location[l] + getDistance(l, k), y = location[r] - getDistance(r, k);
int m = (x + y) >> 1;
if(tt[m] == -1){
if(m >= location[0]) tt[m] = 0;
else tt[m] = 1;
}
if(tt[m]){
location[k] = y;
tt[y] = stype[k] = 0;
if(y < location[l]) l = k;
}else{
location[k] = x;
tt[x] = stype[k] = 1;
if(x > location[r]) r = k;
}
stype[k]++;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4308 KB |
Output is correct |
2 |
Correct |
2 ms |
4308 KB |
Output is correct |
3 |
Correct |
2 ms |
4224 KB |
Output is correct |
4 |
Correct |
2 ms |
4308 KB |
Output is correct |
5 |
Correct |
2 ms |
4232 KB |
Output is correct |
6 |
Correct |
2 ms |
4308 KB |
Output is correct |
7 |
Correct |
2 ms |
4308 KB |
Output is correct |
8 |
Correct |
2 ms |
4308 KB |
Output is correct |
9 |
Correct |
2 ms |
4180 KB |
Output is correct |
10 |
Correct |
2 ms |
4180 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4308 KB |
Output is correct |
2 |
Correct |
2 ms |
4308 KB |
Output is correct |
3 |
Correct |
2 ms |
4180 KB |
Output is correct |
4 |
Correct |
2 ms |
4308 KB |
Output is correct |
5 |
Correct |
2 ms |
4180 KB |
Output is correct |
6 |
Correct |
2 ms |
4308 KB |
Output is correct |
7 |
Correct |
2 ms |
4232 KB |
Output is correct |
8 |
Correct |
3 ms |
4308 KB |
Output is correct |
9 |
Correct |
2 ms |
4180 KB |
Output is correct |
10 |
Correct |
2 ms |
4308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
73 ms |
4480 KB |
Output is correct |
2 |
Correct |
67 ms |
4616 KB |
Output is correct |
3 |
Correct |
67 ms |
4484 KB |
Output is correct |
4 |
Correct |
65 ms |
4484 KB |
Output is correct |
5 |
Correct |
66 ms |
4488 KB |
Output is correct |
6 |
Correct |
71 ms |
4500 KB |
Output is correct |
7 |
Correct |
75 ms |
4488 KB |
Output is correct |
8 |
Correct |
68 ms |
4480 KB |
Output is correct |
9 |
Correct |
67 ms |
4476 KB |
Output is correct |
10 |
Correct |
66 ms |
4496 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
64 ms |
4480 KB |
Output is correct |
2 |
Correct |
69 ms |
4488 KB |
Output is correct |
3 |
Correct |
64 ms |
4480 KB |
Output is correct |
4 |
Correct |
79 ms |
4480 KB |
Output is correct |
5 |
Correct |
71 ms |
4484 KB |
Output is correct |
6 |
Correct |
64 ms |
4428 KB |
Output is correct |
7 |
Correct |
71 ms |
4480 KB |
Output is correct |
8 |
Correct |
70 ms |
4480 KB |
Output is correct |
9 |
Correct |
67 ms |
4492 KB |
Output is correct |
10 |
Correct |
83 ms |
4484 KB |
Output is correct |
11 |
Correct |
68 ms |
4480 KB |
Output is correct |
12 |
Correct |
66 ms |
4488 KB |
Output is correct |
13 |
Correct |
66 ms |
4496 KB |
Output is correct |
14 |
Correct |
69 ms |
4488 KB |
Output is correct |
15 |
Correct |
68 ms |
4484 KB |
Output is correct |
16 |
Correct |
77 ms |
4492 KB |
Output is correct |
17 |
Correct |
66 ms |
4428 KB |
Output is correct |
18 |
Correct |
66 ms |
4492 KB |
Output is correct |
19 |
Correct |
66 ms |
4500 KB |
Output is correct |
20 |
Correct |
69 ms |
4404 KB |
Output is correct |