//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "rail.h"
//#include "grader.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%I64d", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%I64d\n", (n))
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<int,int,hash<int>> ht;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 5e3 + 5;
const double eps = 1e-9;
int dp[MAXN][MAXN];
map<int,int> inv;
int dist(int x, int y) {
if (x == y)
return 0;
if (x > y)
swap(x, y);
if (dp[x][y] == 0)
dp[x][y] = getDistance(x, y);
return dp[x][y];
}
void solve(int l[], int s[], vi& x, int st, int en) {
sort(x.begin(), x.end(), [&](int l, int r) {
return dist(st, l) < dist(st, r);
});
int sgn;
if (s[st] == 1) // ((
sgn = -1;
else // ()
sgn = 1;
for (auto& t: x) {
int val = (dist(en, t) + dist(st, en) - dist(st, t)) / 2;// get from en to en over the next free station
val = l[en] + sgn * val;
if (inv[val] == s[en]) {
l[t] = val + sgn * (dist(st, t) - abs(l[st] - val));
s[t] = s[st];
} else {
l[t] = l[st] - sgn * dist(st, t);
s[t] = s[en];
en = t;
}
inv[l[t]] = s[t];
}
}
void findLocation(int n, int f, int l[], int s[]) {
l[0] = f, s[0] = 1;
inv[l[0]] = 1;
if (n == 1)
return;
int pt = 1; // go the right
for (int i = 2; i < n; i++)
if (dist(0, pt) > dist(0, i))
pt = i;
l[pt] = l[0] + dist(0, pt);
s[pt] = 2;
inv[l[pt]] = 2;
vi x, y;
for (int i = 1; i < n; i++) {
if (i == pt)
continue;
if (dist(pt, i) + dist(pt, 0) == dist(0, i)) {
if (dist(pt, 0) > dist(pt, i)) { // case: (()
l[i] = l[0] + dist(pt, 0) - dist(pt, i);
s[i] = 1;
inv[l[i]] = 1;
} else { // )() and (() are possible
x.pb(i);
}
} else {//()); if pt comes before 0 -> (() or ((( is possible
y.pb(i);
}
}
solve(l, s, x, pt, 0);
solve(l, s, y, 0, pt);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
640 KB |
Output is correct |
2 |
Correct |
3 ms |
768 KB |
Output is correct |
3 |
Correct |
3 ms |
640 KB |
Output is correct |
4 |
Correct |
3 ms |
640 KB |
Output is correct |
5 |
Correct |
2 ms |
640 KB |
Output is correct |
6 |
Correct |
3 ms |
640 KB |
Output is correct |
7 |
Correct |
3 ms |
640 KB |
Output is correct |
8 |
Correct |
3 ms |
640 KB |
Output is correct |
9 |
Correct |
3 ms |
640 KB |
Output is correct |
10 |
Correct |
2 ms |
768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
768 KB |
Output is correct |
2 |
Correct |
3 ms |
640 KB |
Output is correct |
3 |
Correct |
2 ms |
676 KB |
Output is correct |
4 |
Correct |
3 ms |
640 KB |
Output is correct |
5 |
Correct |
3 ms |
640 KB |
Output is correct |
6 |
Correct |
3 ms |
640 KB |
Output is correct |
7 |
Correct |
3 ms |
640 KB |
Output is correct |
8 |
Correct |
2 ms |
640 KB |
Output is correct |
9 |
Correct |
3 ms |
640 KB |
Output is correct |
10 |
Correct |
3 ms |
768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
98 ms |
20108 KB |
Output is correct |
2 |
Correct |
93 ms |
18956 KB |
Output is correct |
3 |
Correct |
125 ms |
22692 KB |
Output is correct |
4 |
Correct |
100 ms |
21112 KB |
Output is correct |
5 |
Correct |
101 ms |
22264 KB |
Output is correct |
6 |
Correct |
117 ms |
24440 KB |
Output is correct |
7 |
Correct |
114 ms |
28408 KB |
Output is correct |
8 |
Correct |
108 ms |
30456 KB |
Output is correct |
9 |
Correct |
100 ms |
19676 KB |
Output is correct |
10 |
Correct |
119 ms |
31872 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
103 ms |
20060 KB |
Output is correct |
2 |
Correct |
108 ms |
18944 KB |
Output is correct |
3 |
Correct |
108 ms |
22824 KB |
Output is correct |
4 |
Correct |
102 ms |
21000 KB |
Output is correct |
5 |
Correct |
110 ms |
22392 KB |
Output is correct |
6 |
Correct |
103 ms |
24312 KB |
Output is correct |
7 |
Correct |
107 ms |
28408 KB |
Output is correct |
8 |
Correct |
115 ms |
30456 KB |
Output is correct |
9 |
Correct |
106 ms |
19648 KB |
Output is correct |
10 |
Correct |
117 ms |
31964 KB |
Output is correct |
11 |
Correct |
106 ms |
29820 KB |
Output is correct |
12 |
Correct |
103 ms |
20520 KB |
Output is correct |
13 |
Correct |
112 ms |
26864 KB |
Output is correct |
14 |
Correct |
135 ms |
23292 KB |
Output is correct |
15 |
Correct |
100 ms |
26232 KB |
Output is correct |
16 |
Correct |
108 ms |
24184 KB |
Output is correct |
17 |
Correct |
110 ms |
23380 KB |
Output is correct |
18 |
Correct |
108 ms |
28388 KB |
Output is correct |
19 |
Correct |
120 ms |
27560 KB |
Output is correct |
20 |
Correct |
98 ms |
18820 KB |
Output is correct |