#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define pi pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
int ask(int i, int j) {
return getDistance(i,j);
}
void findLocation(int n, int p, int ans[], int type[]) {
if (n==1) {
ans[0]=p, type[0]=1; return;
}
vector<int> a(n), b(n), c(n);
vector<int> vis(n,0); vis[0]=1;
int f=0,s=1;
forn(i,n) {
if (vis[i]) continue;
a[i]=ask(0,i);
if (a[i] < a[s]) s=i;
}
vis[s]=1;
b[0]=a[s];
forn(i,n) {
if (vis[i]) continue;
b[i]=ask(s,i);
if (b[i]<b[f]) f=i;
}
vis[f]=1;
ans[0]=p, type[0]=1;
ans[s]=p+a[s], type[s]=2;
ans[f]=ans[s]-b[f], type[f]=1;
vector<pi> l,r;
c[0]=a[f], c[s]=b[f];
forn(i,n) {
if (vis[i]) continue;
int x=a[i], y=b[i], z=b[f];
if (x==a[s]+y) {
l.pb({y,i});
c[i]=y+z;
} else if (y==x-a[s]+2*z) {
r.pb({y-z,i});
c[i]=y-z;
} else assert(0);
}
sort(all(r));
sort(all(l));
int u,v;
u=f, v=s;
for(auto&it:r) {
int d=it.f, i=it.s;
int x=d, y=ask(v,i);
int m=v;
forn(j,n) {
if (!vis[j]) continue;
if (type[j]!=2) continue;
if (ans[j] < ans[v]-y) continue;
if (ans[j] < ans[m]) m=j;
}
if (x == ans[m]-ans[u]+ans[m]-(ans[v]-y)) {
type[i]=1;
ans[i]=ans[v]-y;
} else {
type[i]=2;
ans[i]=ans[u]+x;
v=i;
}
vis[i]=1;
}
u=f,v=s;
for(auto&it:l) {
int d=it.f, i=it.s;
int x=d, y=ask(u,i);
int m=u;
forn(j,n) {
if (!vis[j]) continue;
if (type[j]!=1) continue;
if (ans[j] > ans[u]+y) continue;
if (ans[j] > ans[m]) m=j;
}
if (x == ans[v]-ans[m]+(ans[u]+y)-ans[m]) {
type[i]=2;
ans[i]=ans[u]+y;
} else {
type[i]=1;
ans[i]=ans[v]-x;
u=i;
}
vis[i]=1;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
384 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 |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 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 |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
380 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 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
112 ms |
732 KB |
Output is correct |
2 |
Correct |
108 ms |
664 KB |
Output is correct |
3 |
Correct |
109 ms |
624 KB |
Output is correct |
4 |
Correct |
108 ms |
656 KB |
Output is correct |
5 |
Correct |
109 ms |
680 KB |
Output is correct |
6 |
Correct |
109 ms |
640 KB |
Output is correct |
7 |
Correct |
109 ms |
648 KB |
Output is correct |
8 |
Correct |
112 ms |
640 KB |
Output is correct |
9 |
Correct |
107 ms |
656 KB |
Output is correct |
10 |
Correct |
109 ms |
640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
113 ms |
632 KB |
Output is correct |
2 |
Correct |
118 ms |
636 KB |
Output is correct |
3 |
Correct |
110 ms |
656 KB |
Output is correct |
4 |
Correct |
114 ms |
652 KB |
Output is correct |
5 |
Correct |
125 ms |
772 KB |
Output is correct |
6 |
Correct |
108 ms |
684 KB |
Output is correct |
7 |
Correct |
108 ms |
644 KB |
Output is correct |
8 |
Correct |
107 ms |
664 KB |
Output is correct |
9 |
Correct |
108 ms |
640 KB |
Output is correct |
10 |
Correct |
112 ms |
668 KB |
Output is correct |
11 |
Correct |
108 ms |
648 KB |
Output is correct |
12 |
Correct |
108 ms |
644 KB |
Output is correct |
13 |
Correct |
116 ms |
628 KB |
Output is correct |
14 |
Correct |
106 ms |
652 KB |
Output is correct |
15 |
Correct |
112 ms |
628 KB |
Output is correct |
16 |
Correct |
108 ms |
660 KB |
Output is correct |
17 |
Correct |
108 ms |
680 KB |
Output is correct |
18 |
Correct |
110 ms |
628 KB |
Output is correct |
19 |
Correct |
110 ms |
756 KB |
Output is correct |
20 |
Correct |
109 ms |
588 KB |
Output is correct |