#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include "rail.h"
using namespace std;
const int MAX_BLOCS = (1000 * 1000);
int Type[MAX_BLOCS];
pair <int, int> Dist[MAX_BLOCS];
void findLocation(int nbBlocs, int dep, int AnsPosition[], int AnsType[]) {
Type[dep] = 1;
for (int i = 1; i < nbBlocs; i ++)
{
Dist[i] = {getDistance(0, i), i};
}
sort(Dist + 1, Dist + nbBlocs);
AnsPosition[0] = dep;
AnsType[0] = 1;
AnsPosition[Dist[1].second] = dep + Dist[1].first;
Type[AnsPosition[Dist[1].second]] = AnsType[Dist[1].second] = 2;
int gauche = 0, droite = Dist[1].second;
for (int i = 2; i < nbBlocs; i ++)
{
int id = Dist[i].second;
int lA = getDistance(id, droite), lB = getDistance(id, gauche);
int mid = (AnsPosition[gauche] + AnsPosition[droite] - lA + lB) / 2;
if (Type[mid] == 1 || (Type[mid] == 0 && mid > dep))
{
AnsPosition[id] = AnsPosition[gauche] + lB;
Type[AnsPosition[id]] = AnsType[id] = 2;
}
if (Type[mid] == 2 || (Type[mid] == 0 && mid < dep))
{
AnsPosition[id] = AnsPosition[droite] - lA;
Type[AnsPosition[id]] = AnsType[id] = 1;
}
if (AnsPosition[id] < AnsPosition[gauche])
gauche = id;
if (AnsPosition[id] > AnsPosition[droite])
droite = id;
}
return;
}
# |
결과 |
실행 시간 |
메모리 |
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 |
380 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 |
372 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 |
384 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 |
372 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
87 ms |
4124 KB |
Output is correct |
2 |
Correct |
88 ms |
4212 KB |
Output is correct |
3 |
Correct |
92 ms |
4328 KB |
Output is correct |
4 |
Correct |
87 ms |
4208 KB |
Output is correct |
5 |
Correct |
87 ms |
4216 KB |
Output is correct |
6 |
Correct |
91 ms |
4036 KB |
Output is correct |
7 |
Correct |
88 ms |
4164 KB |
Output is correct |
8 |
Correct |
88 ms |
4204 KB |
Output is correct |
9 |
Correct |
87 ms |
4164 KB |
Output is correct |
10 |
Correct |
91 ms |
4216 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
87 ms |
4064 KB |
Output is correct |
2 |
Correct |
88 ms |
4164 KB |
Output is correct |
3 |
Correct |
87 ms |
4348 KB |
Output is correct |
4 |
Correct |
88 ms |
4208 KB |
Output is correct |
5 |
Correct |
86 ms |
4164 KB |
Output is correct |
6 |
Correct |
87 ms |
4076 KB |
Output is correct |
7 |
Correct |
87 ms |
4164 KB |
Output is correct |
8 |
Correct |
87 ms |
4164 KB |
Output is correct |
9 |
Correct |
87 ms |
4220 KB |
Output is correct |
10 |
Correct |
89 ms |
4220 KB |
Output is correct |
11 |
Correct |
87 ms |
4164 KB |
Output is correct |
12 |
Correct |
86 ms |
4204 KB |
Output is correct |
13 |
Correct |
88 ms |
4204 KB |
Output is correct |
14 |
Correct |
88 ms |
4208 KB |
Output is correct |
15 |
Correct |
87 ms |
4216 KB |
Output is correct |
16 |
Correct |
92 ms |
4292 KB |
Output is correct |
17 |
Correct |
88 ms |
4216 KB |
Output is correct |
18 |
Correct |
96 ms |
4216 KB |
Output is correct |
19 |
Correct |
93 ms |
4200 KB |
Output is correct |
20 |
Correct |
90 ms |
4348 KB |
Output is correct |