#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
struct Val {
int i, val;
};
const int N = 1e4;
int n;
vector<Val> dist;
unordered_map<int, int> id;
void findLocation(int n1, int first, int location[], int stype[]) {
n = n1;
stype[0] = 1;
location[0] = first;
if(n == 1)
return;
for(int i = 1; i < n; i++)
dist.push_back({i, getDistance(0, i)});
sort(dist.begin(), dist.end(),
[](Val a, Val b) {
return a.val < b.val;
});
id[location[0]] = 0;
stype[dist[0].i] = 2;
location[dist[0].i] = first + dist[0].val;
id[location[dist[0].i]] = dist[0].i;
int l = 0, r = dist[0].i;
for(int i = 1; i < n-1; i++) {
int a = getDistance(l, dist[i].i),
b = getDistance(r, dist[i].i),
p = (a - b + location[l] + location[r])/2;
if(id.find(p) == id.end()) {
if(p > first) {
stype[dist[i].i] = 2;
location[dist[i].i] = location[l] + a;
} else {
stype[dist[i].i] = 1;
location[dist[i].i] = location[r] - b;
}
} else {
int j = id[p];
if(stype[j] == 1) {
stype[dist[i].i] = 2;
location[dist[i].i] = location[l] + a;
} else {
stype[dist[i].i] = 1;
location[dist[i].i] = location[r] - b;
}
}
if(stype[dist[i].i] == 1 && location[dist[i].i] < location[l])
l = dist[i].i;
if(stype[dist[i].i] == 2 && location[dist[i].i] > location[r])
r = dist[i].i;
id[location[dist[i].i]] = dist[i].i;
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
376 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
88 ms |
620 KB |
Output is correct |
2 |
Correct |
86 ms |
632 KB |
Output is correct |
3 |
Correct |
84 ms |
620 KB |
Output is correct |
4 |
Correct |
85 ms |
620 KB |
Output is correct |
5 |
Correct |
85 ms |
620 KB |
Output is correct |
6 |
Correct |
85 ms |
708 KB |
Output is correct |
7 |
Correct |
91 ms |
632 KB |
Output is correct |
8 |
Correct |
85 ms |
628 KB |
Output is correct |
9 |
Correct |
87 ms |
624 KB |
Output is correct |
10 |
Correct |
86 ms |
708 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
87 ms |
636 KB |
Output is correct |
2 |
Correct |
96 ms |
632 KB |
Output is correct |
3 |
Correct |
86 ms |
616 KB |
Output is correct |
4 |
Correct |
87 ms |
632 KB |
Output is correct |
5 |
Correct |
97 ms |
708 KB |
Output is correct |
6 |
Correct |
95 ms |
632 KB |
Output is correct |
7 |
Correct |
87 ms |
632 KB |
Output is correct |
8 |
Correct |
85 ms |
632 KB |
Output is correct |
9 |
Correct |
87 ms |
708 KB |
Output is correct |
10 |
Correct |
85 ms |
708 KB |
Output is correct |
11 |
Correct |
88 ms |
624 KB |
Output is correct |
12 |
Correct |
86 ms |
624 KB |
Output is correct |
13 |
Correct |
94 ms |
620 KB |
Output is correct |
14 |
Correct |
85 ms |
628 KB |
Output is correct |
15 |
Correct |
100 ms |
620 KB |
Output is correct |
16 |
Correct |
88 ms |
760 KB |
Output is correct |
17 |
Correct |
86 ms |
624 KB |
Output is correct |
18 |
Correct |
95 ms |
612 KB |
Output is correct |
19 |
Correct |
97 ms |
620 KB |
Output is correct |
20 |
Correct |
89 ms |
620 KB |
Output is correct |