#include "rail.h"
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN=1e5+10;
const int MAXM=1e6+10;
struct Stantia {
int d;
int ind;
};
Stantia st[MAXN];
int dist[2][MAXN];
int um[MAXM];
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;
memset(um,-1,sizeof(um));
for (int i=1;i<n;i++) {
st[i].d=dist[0][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;
um[location[0]]=0; um[location[st[1].ind]]=st[1].ind;
for (int i=0;i<n;i++) {
if (i==st[1].ind) continue;
dist[1][i]=getDistance(st[1].ind,i);
}
int l1, d1;
for (int i=2;i<n;i++) {
int cur=st[i].ind;
if (dist[1][cur]+st[1].d!=st[i].d) {
d1=getDistance(maxi,cur);
l1=(dist[0][maxi]+d1-dist[0][cur])/2;
l1=location[maxi]-l1;
if (um[l1]!=-1 && stype[um[l1]]==2) {
location[cur]=location[maxi]-d1;
stype[cur]=1;
} else {
location[cur]=location[0]+dist[0][cur];
stype[cur]=2;
maxi=cur;
}
///cout << "up " << st[i].ind << ' ' << location[st[i].ind] << endl;
um[location[st[i].ind]]=st[i].ind;
}
}
for (int i=2;i<n;i++) st[i].d=dist[1][st[i].ind];
sort(st+2,st+n,cmp);
for (int i=2;i<n;i++) {
int cur=st[i].ind;
if (dist[1][cur]+st[1].d==dist[0][cur]) {
d1=getDistance(mini,cur);
l1=(dist[1][mini]+d1-dist[1][cur])/2;
l1=location[mini]+l1;
if (um[l1]!=-1 && stype[um[l1]]==1) {
location[cur]=location[mini]+d1;
stype[cur]=2;
} else {
location[cur]=location[st[1].ind]-dist[1][cur];
stype[cur]=1;
mini=cur;
}
///cout << cur << ' ' << location[cur] << endl;
um[location[st[i].ind]]=st[i].ind;
}
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4700 KB |
Output is correct |
2 |
Correct |
1 ms |
4616 KB |
Output is correct |
3 |
Correct |
1 ms |
4700 KB |
Output is correct |
4 |
Correct |
1 ms |
4700 KB |
Output is correct |
5 |
Correct |
1 ms |
4700 KB |
Output is correct |
6 |
Correct |
1 ms |
4700 KB |
Output is correct |
7 |
Correct |
1 ms |
4616 KB |
Output is correct |
8 |
Correct |
1 ms |
4696 KB |
Output is correct |
9 |
Correct |
1 ms |
4700 KB |
Output is correct |
10 |
Correct |
1 ms |
4700 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4700 KB |
Output is correct |
2 |
Correct |
1 ms |
4700 KB |
Output is correct |
3 |
Correct |
1 ms |
4700 KB |
Output is correct |
4 |
Correct |
1 ms |
4696 KB |
Output is correct |
5 |
Correct |
2 ms |
4700 KB |
Output is correct |
6 |
Correct |
1 ms |
4700 KB |
Output is correct |
7 |
Correct |
1 ms |
4696 KB |
Output is correct |
8 |
Correct |
1 ms |
4700 KB |
Output is correct |
9 |
Correct |
1 ms |
4700 KB |
Output is correct |
10 |
Correct |
1 ms |
4700 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
48 ms |
4944 KB |
Output is correct |
2 |
Correct |
50 ms |
4948 KB |
Output is correct |
3 |
Correct |
47 ms |
4744 KB |
Output is correct |
4 |
Correct |
56 ms |
4992 KB |
Output is correct |
5 |
Correct |
49 ms |
4992 KB |
Output is correct |
6 |
Correct |
45 ms |
4944 KB |
Output is correct |
7 |
Correct |
46 ms |
4948 KB |
Output is correct |
8 |
Correct |
47 ms |
4944 KB |
Output is correct |
9 |
Correct |
45 ms |
4988 KB |
Output is correct |
10 |
Correct |
46 ms |
4752 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
47 ms |
4944 KB |
Output is correct |
2 |
Correct |
53 ms |
4944 KB |
Output is correct |
3 |
Correct |
46 ms |
4948 KB |
Output is correct |
4 |
Correct |
49 ms |
4988 KB |
Output is correct |
5 |
Correct |
46 ms |
4752 KB |
Output is correct |
6 |
Correct |
47 ms |
4960 KB |
Output is correct |
7 |
Correct |
46 ms |
4996 KB |
Output is correct |
8 |
Correct |
46 ms |
4944 KB |
Output is correct |
9 |
Correct |
48 ms |
4992 KB |
Output is correct |
10 |
Correct |
45 ms |
4988 KB |
Output is correct |
11 |
Correct |
45 ms |
4748 KB |
Output is correct |
12 |
Correct |
45 ms |
4756 KB |
Output is correct |
13 |
Correct |
46 ms |
4948 KB |
Output is correct |
14 |
Correct |
55 ms |
4748 KB |
Output is correct |
15 |
Correct |
45 ms |
4752 KB |
Output is correct |
16 |
Correct |
48 ms |
4988 KB |
Output is correct |
17 |
Correct |
48 ms |
4948 KB |
Output is correct |
18 |
Correct |
55 ms |
4948 KB |
Output is correct |
19 |
Correct |
47 ms |
4944 KB |
Output is correct |
20 |
Correct |
45 ms |
4944 KB |
Output is correct |