#include <bits/stdc++.h>
#include "rail.h"
using namespace std;
#define pb push_back
#define eb emplace_back
#define ll long long
#define pii pair < int, int >
#define fr first
#define sc second
#define mk make_pair
#define sz(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define Ok puts("ok");
#define whatis(x) cerr << #x << " = " << x << endl;
#define pause system("pause");
#define random (rand() ^ (rand() << 15))
const int N = (int)5000 + 7;
const int inf = (int)1e9 + 7;
int dis[N][N];
int getdis(int i, int j) {
if (i == j) return 0;
if (dis[i][j] != 0) return dis[i][j];
dis[i][j] = dis[j][i] = getDistance(i, j);
return dis[i][j];
}
set < int > sd, su;
pii ar[N];
int sec;
void findLocation(int n, int first, int location[], int stype[]) {
int L, R;
for (int i = 1; i < n; i++) {
ar[i] = mk(getdis(0, i), i);
}
sort(ar + 1, ar + n);
L = 0;
stype[L] = 1;
R = ar[1].sc;
stype[R] = 2;
location[L] = first;
location[R] = first + ar[1].fr;
sec = R;
set < int > :: iterator to;
sd.insert(first);
su.insert(location[R]);
for (int j = 2; j < n; j++) {
int i = ar[j].sc;
int dist = ar[j].fr;
int distsec = getdis(sec, i);
if (dist == distsec + ar[1].fr && location[sec] - distsec < first) {
int distL = getdis(L, i);
int p = location[L] + distL;
to = sd.lower_bound(p);
to--;
int rr = *to;
if (location[sec] - rr + p - rr == distsec) {
stype[i] = 2;
location[i] = p;
} else {
stype[i] = 1;
location[i] = location[sec] - distsec;
sd.insert(location[i]);
L = i;
}
} else {
int distR = getdis(R, i);
int p = location[R] - distR;
to = su.upper_bound(p);
int rr = *to;
if (rr - first + rr - p == dist) {
stype[i] = 1;
location[i] = p;
} else {
stype[i] = 2;
location[i] = first + dist;
su.insert(location[i]);
R = i;
}
}
}
// for (int i = 0; i < n; i++) {
// cerr << location[i] << ' ';
// }
// cerr << '\n';
// for (int i = 0; i < n; i++) {
// cerr << stype[i] << ' ';
// }
// cerr << '\n';
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
760 KB |
Output is correct |
2 |
Correct |
2 ms |
760 KB |
Output is correct |
3 |
Correct |
2 ms |
920 KB |
Output is correct |
4 |
Correct |
2 ms |
996 KB |
Output is correct |
5 |
Correct |
2 ms |
996 KB |
Output is correct |
6 |
Correct |
2 ms |
996 KB |
Output is correct |
7 |
Correct |
2 ms |
996 KB |
Output is correct |
8 |
Correct |
2 ms |
996 KB |
Output is correct |
9 |
Correct |
3 ms |
996 KB |
Output is correct |
10 |
Correct |
3 ms |
996 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
996 KB |
Output is correct |
2 |
Correct |
3 ms |
1000 KB |
Output is correct |
3 |
Correct |
2 ms |
1000 KB |
Output is correct |
4 |
Correct |
2 ms |
1000 KB |
Output is correct |
5 |
Correct |
2 ms |
1000 KB |
Output is correct |
6 |
Correct |
2 ms |
1128 KB |
Output is correct |
7 |
Correct |
2 ms |
1128 KB |
Output is correct |
8 |
Correct |
2 ms |
1128 KB |
Output is correct |
9 |
Correct |
2 ms |
1128 KB |
Output is correct |
10 |
Correct |
2 ms |
1128 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
126 ms |
56700 KB |
Output is correct |
2 |
Correct |
150 ms |
56700 KB |
Output is correct |
3 |
Correct |
126 ms |
60968 KB |
Output is correct |
4 |
Correct |
132 ms |
60968 KB |
Output is correct |
5 |
Correct |
127 ms |
60968 KB |
Output is correct |
6 |
Correct |
129 ms |
60968 KB |
Output is correct |
7 |
Correct |
128 ms |
60968 KB |
Output is correct |
8 |
Correct |
123 ms |
60968 KB |
Output is correct |
9 |
Correct |
126 ms |
60968 KB |
Output is correct |
10 |
Correct |
125 ms |
60968 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
122 ms |
60968 KB |
Output is correct |
2 |
Correct |
124 ms |
60968 KB |
Output is correct |
3 |
Correct |
129 ms |
61012 KB |
Output is correct |
4 |
Correct |
127 ms |
61012 KB |
Output is correct |
5 |
Correct |
126 ms |
61012 KB |
Output is correct |
6 |
Correct |
129 ms |
61012 KB |
Output is correct |
7 |
Correct |
139 ms |
61012 KB |
Output is correct |
8 |
Correct |
138 ms |
61012 KB |
Output is correct |
9 |
Correct |
134 ms |
61012 KB |
Output is correct |
10 |
Correct |
147 ms |
61012 KB |
Output is correct |
11 |
Correct |
131 ms |
61012 KB |
Output is correct |
12 |
Correct |
135 ms |
61012 KB |
Output is correct |
13 |
Correct |
127 ms |
61308 KB |
Output is correct |
14 |
Correct |
127 ms |
61308 KB |
Output is correct |
15 |
Correct |
125 ms |
61308 KB |
Output is correct |
16 |
Correct |
126 ms |
61308 KB |
Output is correct |
17 |
Correct |
135 ms |
61308 KB |
Output is correct |
18 |
Correct |
136 ms |
61308 KB |
Output is correct |
19 |
Correct |
130 ms |
61548 KB |
Output is correct |
20 |
Correct |
123 ms |
61548 KB |
Output is correct |