#include "rail.h"
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
const int MAXN=1e5+10;
const int MAXM=1e6+10;
struct Stantia {
int d;
int ind;
};
Stantia st[MAXN];
int dist[MAXN];
int um[MAXM];
set <int> lef, ri;
bool cmp(Stantia a, Stantia b) {
return a.d<b.d;
}
void findLocation (int n, int first, int location[], int stype[]) {
location[0]=first; stype[0]=1;
for (int i=1;i<n;i++) {
st[i].d=dist[i]=getDistance(0,i);
st[i].ind=i;
}
sort(st+1,st+n,cmp);
location[st[1].ind]=first+st[1].d;
stype[st[1].ind]=2;
int mini=0, maxi=st[1].ind;
lef.insert(-first);
ri.insert(location[st[1].ind]);
um[location[0]]=0; um[location[st[1].ind]]=st[1].ind;
int l1, d1, d2, cur_c, cur_ind;
for (int i=2;i<n;i++) {
d1=getDistance(st[i].ind,st[1].ind);
if (d1+st[1].d==st[i].d && st[i].d>2*st[1].d) {
l1=location[mini]+(st[i].d-dist[mini]);
cur_c=-(*lef.lower_bound(-l1));
cur_ind=um[cur_c];
d2=getDistance(cur_ind,st[i].ind);
if (mini==0 || d2+dist[cur_ind]!=st[i].d) {
location[st[i].ind]=location[st[1].ind]-(st[i].d-st[1].d);
stype[st[i].ind]=1;
lef.insert(-location[st[i].ind]);
mini=st[i].ind;
} else {
location[st[i].ind]=location[cur_ind]+d2;
stype[st[i].ind]=2;
}
} else {
l1=location[maxi]-(st[i].d-dist[maxi]);
cur_c=(*ri.lower_bound(l1));
cur_ind=um[cur_c];
d2=getDistance(cur_ind,st[i].ind);
if (d2+dist[cur_ind]!=st[i].d) {
location[st[i].ind]=location[0]+st[i].d;
stype[st[i].ind]=2;
ri.insert(location[st[i].ind]);
} else {
location[st[i].ind]=location[cur_ind]-d2;
stype[st[i].ind]=1;
}
}
um[location[st[i].ind]]=st[i].ind;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
3 |
Correct |
1 ms |
2396 KB |
Output is correct |
4 |
Correct |
2 ms |
2392 KB |
Output is correct |
5 |
Correct |
1 ms |
2396 KB |
Output is correct |
6 |
Correct |
1 ms |
2396 KB |
Output is correct |
7 |
Correct |
1 ms |
2404 KB |
Output is correct |
8 |
Correct |
1 ms |
2396 KB |
Output is correct |
9 |
Correct |
1 ms |
2576 KB |
Output is correct |
10 |
Correct |
1 ms |
2392 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Incorrect |
1 ms |
2568 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
47 ms |
6800 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
47 ms |
7004 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |