#include<bits/stdc++.h>
#include "rail.h"
using namespace std;
int mi=0x3f3f3f3f;
int st[2][55555],d[55555][2],v[2222222],o,oo;
int cmp(int a,int b){
return d[a][0]<d[b][0];
}
void findLocation(int n,int fi,int l[],int s[]){
l[0]=fi;
s[0]=v[l[0]]=1;
if(n==1) return ;
int id=0;
for(int i=1;i<n;i++){
d[i][0]=getDistance(0,i);
if(d[i][0]<mi){
mi=d[i][0];
id=i;
}
}
l[id]=l[0]+mi;
s[id]=2;
v[l[id]]=2;
for(int i=1;i<n;i++){
if(i==id) continue;
d[i][1]=getDistance(i,id);
if(d[i][1]+mi==d[i][0]){
if(d[i][1]<mi){
l[i]=l[id]-d[i][1];
v[l[i]]=s[i]=1;
}else{
st[0][++o]=i;
}
}else{
st[1][++oo]=i;
}
}
sort(st[0]+1,st[0]+o+1,cmp);
sort(st[1]+1,st[1]+oo+1,cmp);
int la=0,now=0;
for(int i=1;i<=o;i++){
now=st[0][i];
int len=(d[la][1]-d[now][1]+getDistance(la,now))/2;
if(v[l[la]+len]==1){
s[now]=2;
l[now]=2*(l[la]+len)+d[now][1]-l[id];
}else{
la=now;
s[now]=1;
l[now]=l[id]-d[now][1];
}
v[l[now]]=s[now];
}
la=id;
for(int i=1;i<=oo;i++){
now=st[1][i];
int len=(d[la][0]-d[now][0]+getDistance(la,now))/2;
if(v[l[la]-len]==2){
s[now]=1;
l[now]=2*(l[la]-len)-d[now][0]-l[0];
}else{
la=now;
s[now]=2;
l[now]=l[0]+d[now][0];
}
v[l[now]]=s[now];
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
384 KB |
Output is correct |
| 6 |
Correct |
0 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 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 |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
388 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 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 |
340 KB |
Output is correct |
| 8 |
Correct |
0 ms |
340 KB |
Output is correct |
| 9 |
Correct |
0 ms |
340 KB |
Output is correct |
| 10 |
Correct |
0 ms |
340 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
48 ms |
4092 KB |
Output is correct |
| 2 |
Correct |
46 ms |
4172 KB |
Output is correct |
| 3 |
Correct |
45 ms |
4300 KB |
Output is correct |
| 4 |
Correct |
46 ms |
4340 KB |
Output is correct |
| 5 |
Correct |
46 ms |
4232 KB |
Output is correct |
| 6 |
Correct |
46 ms |
4088 KB |
Output is correct |
| 7 |
Correct |
47 ms |
4172 KB |
Output is correct |
| 8 |
Correct |
46 ms |
4228 KB |
Output is correct |
| 9 |
Correct |
50 ms |
4224 KB |
Output is correct |
| 10 |
Correct |
46 ms |
4228 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
45 ms |
4092 KB |
Output is correct |
| 2 |
Correct |
46 ms |
4228 KB |
Output is correct |
| 3 |
Correct |
46 ms |
4340 KB |
Output is correct |
| 4 |
Correct |
46 ms |
4224 KB |
Output is correct |
| 5 |
Correct |
46 ms |
4232 KB |
Output is correct |
| 6 |
Correct |
46 ms |
4092 KB |
Output is correct |
| 7 |
Correct |
47 ms |
4212 KB |
Output is correct |
| 8 |
Correct |
46 ms |
4220 KB |
Output is correct |
| 9 |
Correct |
46 ms |
4216 KB |
Output is correct |
| 10 |
Correct |
52 ms |
4228 KB |
Output is correct |
| 11 |
Correct |
50 ms |
4096 KB |
Output is correct |
| 12 |
Correct |
46 ms |
4232 KB |
Output is correct |
| 13 |
Correct |
46 ms |
4224 KB |
Output is correct |
| 14 |
Correct |
46 ms |
4228 KB |
Output is correct |
| 15 |
Correct |
53 ms |
4212 KB |
Output is correct |
| 16 |
Correct |
46 ms |
4360 KB |
Output is correct |
| 17 |
Correct |
46 ms |
4300 KB |
Output is correct |
| 18 |
Correct |
46 ms |
4220 KB |
Output is correct |
| 19 |
Correct |
46 ms |
4300 KB |
Output is correct |
| 20 |
Correct |
48 ms |
4340 KB |
Output is correct |
