#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
void findLocation(int n, int first, int location[], int stype[]) {
memset(stype, -1, sizeof(stype[0]) * n);
location[0] = first;
stype[0] = 1;
if (n == 1) {
return;
}
vector<int> dist0(n), distP(n);
for (int i = 1; i < n; ++i) {
dist0[i] = getDistance(i, 0);
}
int p = min_element(dist0.begin() + 1, dist0.end()) - dist0.begin();
location[p] = first + dist0[p];
stype[p] = 2;
for (int i = 0; i < n; ++i) {
if (i != p) {
distP[i] = getDistance(i, p);
}
}
vector<pair<int, int>> L, R;
for (int i = 0; i < n; ++i) {
if (i != p && (i == 0 || dist0[i] == dist0[p] + distP[i])) {
L.emplace_back(distP[i], i);
} else {
R.emplace_back(dist0[i], i);
}
}
set<int> st;
sort(L.begin(), L.end());
int last_c = -1;
for (auto [x, i]: L) {
bool c = last_c == -1;
int dist;
if (!c) {
dist = getDistance(last_c, i);
int kek = (distP[i] + dist - distP[last_c]);
int cord = location[p] - (distP[i] - kek / 2);
c = kek % 2 == 0 && !st.count(cord);
}
if (c) {
location[i] = location[p] - distP[i];
stype[last_c = i] = 1;
st.insert(location[i]);
} else {
location[i] = location[last_c] + dist;
stype[i] = 2;
}
}
st.clear();
int last_d = -1;
sort(R.begin(), R.end());
for (auto [x, i]: R) {
int dist;
bool d = last_d == -1;
if (!d) {
dist = getDistance(last_d, i);
int kek = (dist0[i] + dist - dist0[last_d]);
int cord = location[0] + (dist0[i] - kek / 2);
d = kek % 2 == 0 && !st.count(cord);
}
if (d) {
location[i] = location[0] + dist0[i];
stype[last_d = i] = 2;
st.insert(location[i]);
} else {
location[i] = location[last_d] - dist;
stype[i] = 1;
}
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 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 |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
380 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
0 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
68 ms |
624 KB |
Output is correct |
2 |
Correct |
64 ms |
624 KB |
Output is correct |
3 |
Correct |
64 ms |
588 KB |
Output is correct |
4 |
Correct |
65 ms |
632 KB |
Output is correct |
5 |
Correct |
65 ms |
636 KB |
Output is correct |
6 |
Correct |
66 ms |
632 KB |
Output is correct |
7 |
Correct |
69 ms |
628 KB |
Output is correct |
8 |
Correct |
64 ms |
640 KB |
Output is correct |
9 |
Correct |
65 ms |
628 KB |
Output is correct |
10 |
Correct |
65 ms |
628 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
65 ms |
632 KB |
Output is correct |
2 |
Correct |
71 ms |
716 KB |
Output is correct |
3 |
Correct |
65 ms |
636 KB |
Output is correct |
4 |
Correct |
66 ms |
628 KB |
Output is correct |
5 |
Correct |
65 ms |
636 KB |
Output is correct |
6 |
Correct |
66 ms |
636 KB |
Output is correct |
7 |
Correct |
67 ms |
640 KB |
Output is correct |
8 |
Correct |
65 ms |
588 KB |
Output is correct |
9 |
Correct |
65 ms |
628 KB |
Output is correct |
10 |
Correct |
65 ms |
588 KB |
Output is correct |
11 |
Correct |
65 ms |
640 KB |
Output is correct |
12 |
Correct |
66 ms |
624 KB |
Output is correct |
13 |
Correct |
67 ms |
636 KB |
Output is correct |
14 |
Correct |
68 ms |
628 KB |
Output is correct |
15 |
Correct |
66 ms |
624 KB |
Output is correct |
16 |
Correct |
66 ms |
632 KB |
Output is correct |
17 |
Correct |
65 ms |
624 KB |
Output is correct |
18 |
Correct |
65 ms |
636 KB |
Output is correct |
19 |
Correct |
66 ms |
640 KB |
Output is correct |
20 |
Correct |
65 ms |
640 KB |
Output is correct |