#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
using idata = vector<int>;
using bdata = vector<bool>;
template<typename T>
using lpq = priority_queue<T, vector<T>, greater<T>>;
using ii = pair<int, int>;
idata distance0;
const int DTYPE = 2;
const int CTYPE = 1;
void findLocation(int N, int first, int location[], int stype[])
{
location[0] = first;
stype [0] = 1;
distance0.resize(N, -1);
int minD = 1e9;
int minP = -1;
for (int i = 1; i < N; i ++) {
distance0[i] = getDistance(0, i);
if (distance0[i] >= minD) continue ;
minD = distance0[i];
minP = i;
}
int lefD = minP;
int rigD = minP;
location[minP] = first + minD;
stype [minP] = DTYPE;
int lefC = -1;
lpq<ii> queue;
for (int i = 1; i < N; i ++)
if (i != minP)
queue.push({ distance0[i], i });
set<int> rigDPos = { first + minD };
set<int> lefCPos = { };
while (queue.size() != 0) {
const auto nextDP = queue.top(); queue.pop();
int next = nextDP.second;
int nextDist = getDistance(lefD, next);
int offDist = nextDist + minD;
int resDist = distance0[next];
if (resDist == offDist) {
bool isLefC = true;
int passDist;
if (lefC != -1) {
passDist = getDistance(lefC, next);
int potPos = location[lefC] + passDist;
auto it = lefCPos.lower_bound( potPos ); it --;
int potLefC = *it;
int potDist = first + 2 * minD + potPos - 2 * potLefC;
isLefC = potDist != resDist;
}
if (isLefC) {
lefC = next;
location[next] = first + minD - nextDist;
stype [next] = CTYPE;
lefCPos.insert( location[next] );
} else {
location[next] = passDist + location[lefC];
stype [next] = DTYPE;
}
} else {
bool isRigD;
int passDist = getDistance(rigD, next);
int potLocat = location[rigD] - passDist;
int potRigD = *rigDPos.upper_bound(potLocat);
int potDist = 2 * potRigD - potLocat - first;
isRigD = potDist != resDist;
if (isRigD) {
rigD = next;
location[next] = first + distance0[next];
stype [next] = DTYPE;
rigDPos.insert(location[next]);
} else {
location[next] = location[rigD] - passDist;
stype [next] = CTYPE;
}
}
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
50 ms |
576 KB |
Output is correct |
2 |
Correct |
44 ms |
672 KB |
Output is correct |
3 |
Correct |
45 ms |
632 KB |
Output is correct |
4 |
Correct |
47 ms |
632 KB |
Output is correct |
5 |
Correct |
45 ms |
636 KB |
Output is correct |
6 |
Correct |
45 ms |
588 KB |
Output is correct |
7 |
Correct |
44 ms |
624 KB |
Output is correct |
8 |
Correct |
45 ms |
628 KB |
Output is correct |
9 |
Correct |
46 ms |
624 KB |
Output is correct |
10 |
Correct |
48 ms |
656 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
44 ms |
584 KB |
Output is correct |
2 |
Correct |
47 ms |
624 KB |
Output is correct |
3 |
Correct |
52 ms |
648 KB |
Output is correct |
4 |
Correct |
46 ms |
652 KB |
Output is correct |
5 |
Correct |
44 ms |
640 KB |
Output is correct |
6 |
Correct |
44 ms |
624 KB |
Output is correct |
7 |
Correct |
48 ms |
628 KB |
Output is correct |
8 |
Correct |
51 ms |
640 KB |
Output is correct |
9 |
Correct |
44 ms |
588 KB |
Output is correct |
10 |
Correct |
45 ms |
588 KB |
Output is correct |
11 |
Correct |
43 ms |
640 KB |
Output is correct |
12 |
Correct |
44 ms |
632 KB |
Output is correct |
13 |
Correct |
46 ms |
644 KB |
Output is correct |
14 |
Correct |
45 ms |
644 KB |
Output is correct |
15 |
Correct |
47 ms |
588 KB |
Output is correct |
16 |
Correct |
44 ms |
636 KB |
Output is correct |
17 |
Correct |
44 ms |
628 KB |
Output is correct |
18 |
Correct |
44 ms |
644 KB |
Output is correct |
19 |
Correct |
45 ms |
588 KB |
Output is correct |
20 |
Correct |
48 ms |
640 KB |
Output is correct |