#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5000 + 10;
int dis[maxn], a[maxn];
int loc[maxn], type[maxn];
map<int,int> mp;
void findLocation(int n, int first, int location[], int stype[]){
loc[0] = first, type[0] = 1;
if (n == 1)
return;
for (int i = 1; i < n; i++)
dis[i] = getDistance(0,i);
for (int i = 1; i < n; i++)
a[i] = i;
sort(a+1, a+n, [](int a, int b){
return dis[a] < dis[b];
});
loc[a[1]] = first+dis[a[1]], type[a[1]] = 2;
int l = 0, r = a[1];
mp[loc[0]] = 1, mp[loc[a[1]]] = 2;
for (int _ = 2; _ < n; _++){
int i = a[_];
int dl = loc[l]+getDistance(l,i), dr = loc[r]-getDistance(r,i), mid = (dl+dr) / 2;
if (mp[mid] == 1 or (mp[mid] == 0 and mid > first)){
loc[i] = dl;
type[i] = 2;
if (dl > loc[r])
r = i;
}
else{
loc[i] = dr;
type[i] = 1;
if (dr < loc[l])
l = i;
}
mp[loc[i]] = type[i];
}
for (int i = 0; i < n; i++)
location[i] = loc[i], stype[i] = type[i];
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
0 ms |
384 KB |
Output is correct |
| 5 |
Correct |
0 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| 8 |
Correct |
0 ms |
384 KB |
Output is correct |
| 9 |
Correct |
0 ms |
384 KB |
Output is correct |
| 10 |
Correct |
1 ms |
384 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
0 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
384 KB |
Output is correct |
| 6 |
Correct |
0 ms |
384 KB |
Output is correct |
| 7 |
Correct |
0 ms |
384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
384 KB |
Output is correct |
| 10 |
Correct |
0 ms |
384 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
84 ms |
760 KB |
Output is correct |
| 2 |
Correct |
86 ms |
760 KB |
Output is correct |
| 3 |
Correct |
84 ms |
760 KB |
Output is correct |
| 4 |
Correct |
85 ms |
760 KB |
Output is correct |
| 5 |
Correct |
83 ms |
848 KB |
Output is correct |
| 6 |
Correct |
84 ms |
760 KB |
Output is correct |
| 7 |
Correct |
85 ms |
760 KB |
Output is correct |
| 8 |
Correct |
88 ms |
760 KB |
Output is correct |
| 9 |
Correct |
87 ms |
760 KB |
Output is correct |
| 10 |
Correct |
87 ms |
760 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
84 ms |
760 KB |
Output is correct |
| 2 |
Correct |
86 ms |
760 KB |
Output is correct |
| 3 |
Correct |
87 ms |
720 KB |
Output is correct |
| 4 |
Correct |
86 ms |
760 KB |
Output is correct |
| 5 |
Correct |
85 ms |
720 KB |
Output is correct |
| 6 |
Correct |
84 ms |
760 KB |
Output is correct |
| 7 |
Correct |
88 ms |
760 KB |
Output is correct |
| 8 |
Correct |
85 ms |
760 KB |
Output is correct |
| 9 |
Correct |
100 ms |
760 KB |
Output is correct |
| 10 |
Correct |
87 ms |
760 KB |
Output is correct |
| 11 |
Correct |
86 ms |
760 KB |
Output is correct |
| 12 |
Correct |
86 ms |
760 KB |
Output is correct |
| 13 |
Correct |
86 ms |
1016 KB |
Output is correct |
| 14 |
Correct |
85 ms |
760 KB |
Output is correct |
| 15 |
Correct |
86 ms |
760 KB |
Output is correct |
| 16 |
Correct |
84 ms |
760 KB |
Output is correct |
| 17 |
Correct |
84 ms |
888 KB |
Output is correct |
| 18 |
Correct |
84 ms |
760 KB |
Output is correct |
| 19 |
Correct |
84 ms |
760 KB |
Output is correct |
| 20 |
Correct |
85 ms |
760 KB |
Output is correct |
