#include "rail.h"
#include <bits/stdc++.h>
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;
map<pair<int,int>,int> m;
int get(int a,int b){
if(a>b){
swap(a,b);
}
if(a==b){
return 0;
}
if(m.find(pair<int,int>(a,b))==m.end()){
m[pair<int,int>(a,b)]=getDistance(a,b);
}
return m[{a,b}];
}
void findLocation(int n, int fr, int l[], int s[]){
vector<int> d0(n),d1(n);
int mn=-1;
for(int i=1;i<n;i++){
d0[i]=get(0,i);
if(mn==-1 || d0[i]<d0[mn]){
mn=i;
}
}
l[0]=fr;
s[0]=1;
l[mn]=fr+d0[mn];
s[mn]=2;
vector<int> d;
vector<pair<int,int> > a,b;
for(int i=0;i<n;i++){
d1[i]=get(mn,i);
if(i==mn || i==0){
continue;
}
if(d0[i]==d1[i]+d0[mn]){
if(d1[i]<d0[mn]){
l[i]=l[mn]-d1[i];
s[i]=1;
d.push_back(-l[i]);
}
else{
a.push_back({d1[i],i});
}
}
else{
b.push_back({d0[i],i});
}
}
//b -> right, a -> left
d.push_back(-l[0]);
sort(a.begin(),a.end());
{
int u=0;
for(auto h:a){
int x=get(u,h.sc);
int f=l[u]+x;
int y=-(*lower_bound(d.begin(),d.end(),-f));
if(y==f || h.fs!=f+l[mn]-2*y){
l[h.sc]=l[mn]-d1[h.sc];
s[h.sc]=1;
d.push_back(-l[h.sc]);
u=h.sc;
}
else{
s[h.sc]=2;
l[h.sc]=f;
}
}
}
sort(b.begin(),b.end());
{
int u=mn;
vector<int> c;
c.push_back(l[mn]);
for(auto h:b){
int x=get(u,h.sc);
int f=l[u]-x;
int y=*lower_bound(c.begin(),c.end(),f);
if(y==f || h.fs!=2*y-l[0]-f){
l[h.sc]=l[0]+d0[h.sc];
s[h.sc]=2;
c.push_back(l[h.sc]);
u=h.sc;
}
else{
s[h.sc]=1;
l[h.sc]=f;
}
}
}
}
# |
결과 |
실행 시간 |
메모리 |
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 |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
384 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 |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
380 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
384 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 |
48 ms |
1528 KB |
Output is correct |
2 |
Correct |
50 ms |
1536 KB |
Output is correct |
3 |
Correct |
48 ms |
1524 KB |
Output is correct |
4 |
Correct |
48 ms |
1484 KB |
Output is correct |
5 |
Correct |
49 ms |
1532 KB |
Output is correct |
6 |
Correct |
49 ms |
1500 KB |
Output is correct |
7 |
Correct |
49 ms |
1416 KB |
Output is correct |
8 |
Correct |
49 ms |
1540 KB |
Output is correct |
9 |
Correct |
49 ms |
1524 KB |
Output is correct |
10 |
Correct |
49 ms |
1472 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
49 ms |
1484 KB |
Output is correct |
2 |
Correct |
49 ms |
1528 KB |
Output is correct |
3 |
Correct |
48 ms |
1536 KB |
Output is correct |
4 |
Correct |
49 ms |
1536 KB |
Output is correct |
5 |
Correct |
49 ms |
1532 KB |
Output is correct |
6 |
Correct |
51 ms |
1524 KB |
Output is correct |
7 |
Correct |
49 ms |
1520 KB |
Output is correct |
8 |
Correct |
49 ms |
1528 KB |
Output is correct |
9 |
Correct |
49 ms |
1484 KB |
Output is correct |
10 |
Correct |
50 ms |
1536 KB |
Output is correct |
11 |
Correct |
48 ms |
1520 KB |
Output is correct |
12 |
Correct |
49 ms |
1520 KB |
Output is correct |
13 |
Correct |
51 ms |
1536 KB |
Output is correct |
14 |
Correct |
49 ms |
1408 KB |
Output is correct |
15 |
Correct |
58 ms |
1524 KB |
Output is correct |
16 |
Correct |
50 ms |
1484 KB |
Output is correct |
17 |
Correct |
49 ms |
1528 KB |
Output is correct |
18 |
Correct |
49 ms |
1532 KB |
Output is correct |
19 |
Correct |
50 ms |
1524 KB |
Output is correct |
20 |
Correct |
53 ms |
1524 KB |
Output is correct |