#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
int dp[5000][5000];
int tot = 0;
int get(int a,int b){
if(a == b)
return 0;
if(dp[a][b] || dp[b][a])
return max(dp[a][b],dp[b][a]);
tot--;
assert(tot >= 0);
return dp[a][b] = getDistance(a,b);
}
void findLocation(int n, int first, int location[], int stype[]){
tot = n * (n-1)/2;
for(int i = 0;i<n;i++){
stype[i] = 0;
for(int j = 0;j<n;j++){
dp[i][j] = 0;
}
}
location[0] = first;
stype[0] = 1;
if(n == 1)return;
vector<int> ord0;
for(int i = 0;i<n;i++){
if(i != 0){
ord0.push_back(i);
}
}
sort(ord0.begin(),ord0.end(),[&](int a,int b){
return get(0,a) < get(0,b);
});
int posD = ord0[0];
location[posD] = location[0] + get(0,posD);
stype[posD] = 2;
vector<int> v;
v.push_back(0);
for(int i = 0;i<ord0.size();i++){
if(stype[ord0[i]])continue;
if(get(0,ord0[i]) != get(posD,ord0[i]) + get(0,posD))continue;
if(get(0,ord0[i]) < 2 * get(0,posD)){
stype[ord0[i]] = 1;
location[ord0[i]] = location[posD] - (get(0,ord0[i]) - get(0,posD));
continue;
}
int candpos = location[v.back()] + get(v.back(),ord0[i]);
int closest = -1;
for(auto u:v){
if(location[u] < candpos){
if(closest == -1 || location[closest] < location[u]){
closest = u;
}
}
}
if(closest == 0 || get(0,ord0[i]) != get(0,closest) + (candpos - location[closest])){
v.push_back(ord0[i]);
stype[ord0[i]] = 1;
location[ord0[i]] = location[posD] - (get(0,ord0[i]) - get(0,posD));
}
else{
stype[ord0[i]] = 2;
location[ord0[i]] = candpos;
}
}
// for(int i = 0;i<n;i++){
// if(stype[i]){
// cout << i << endl;
// cout << stype[i] << ' ' << location[i] << endl;
// }
// }
v.clear();
v.push_back(posD);
for(int i = 0;i<ord0.size();i++){
if(stype[ord0[i]])continue;
int candpos = location[v.back()] - get(v.back(),ord0[i]);
int closest = -1;
for(auto u:v){
if(location[u] > candpos){
if(closest == -1 || location[closest] > location[u]){
closest = u;
}
}
}
if(get(0,ord0[i]) != get(0,closest) + (location[closest] - candpos)){
v.push_back(ord0[i]);
stype[ord0[i]] = 2;
location[ord0[i]] = location[0] + get(0,ord0[i]);
}
else{
stype[ord0[i]] = 1;
location[ord0[i]] = candpos;
}
}
// for(int i = 0;i<n;i++){
// if(stype[i]){
// cout << i << endl;
// cout << stype[i] << ' ' << location[i] << endl;
// }
// }
}
Compilation message
rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:40:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | for(int i = 0;i<ord0.size();i++){
| ~^~~~~~~~~~~~
rail.cpp:75:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for(int i = 0;i<ord0.size();i++){
| ~^~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
724 KB |
Output is correct |
2 |
Correct |
1 ms |
764 KB |
Output is correct |
3 |
Correct |
1 ms |
724 KB |
Output is correct |
4 |
Correct |
1 ms |
724 KB |
Output is correct |
5 |
Correct |
1 ms |
724 KB |
Output is correct |
6 |
Correct |
1 ms |
724 KB |
Output is correct |
7 |
Correct |
1 ms |
724 KB |
Output is correct |
8 |
Correct |
1 ms |
724 KB |
Output is correct |
9 |
Correct |
1 ms |
724 KB |
Output is correct |
10 |
Correct |
1 ms |
724 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
724 KB |
Output is correct |
2 |
Correct |
1 ms |
724 KB |
Output is correct |
3 |
Correct |
1 ms |
724 KB |
Output is correct |
4 |
Correct |
1 ms |
772 KB |
Output is correct |
5 |
Correct |
1 ms |
768 KB |
Output is correct |
6 |
Correct |
1 ms |
724 KB |
Output is correct |
7 |
Correct |
1 ms |
772 KB |
Output is correct |
8 |
Correct |
1 ms |
724 KB |
Output is correct |
9 |
Correct |
1 ms |
724 KB |
Output is correct |
10 |
Correct |
1 ms |
816 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
96 ms |
98400 KB |
Output is correct |
2 |
Correct |
88 ms |
98296 KB |
Output is correct |
3 |
Correct |
81 ms |
98296 KB |
Output is correct |
4 |
Correct |
84 ms |
98348 KB |
Output is correct |
5 |
Correct |
91 ms |
98296 KB |
Output is correct |
6 |
Correct |
91 ms |
98372 KB |
Output is correct |
7 |
Correct |
91 ms |
98284 KB |
Output is correct |
8 |
Correct |
93 ms |
98296 KB |
Output is correct |
9 |
Correct |
85 ms |
98336 KB |
Output is correct |
10 |
Correct |
89 ms |
98300 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
94 ms |
98424 KB |
Output is correct |
2 |
Correct |
90 ms |
98396 KB |
Output is correct |
3 |
Correct |
87 ms |
98292 KB |
Output is correct |
4 |
Correct |
91 ms |
98288 KB |
Output is correct |
5 |
Correct |
89 ms |
98304 KB |
Output is correct |
6 |
Correct |
89 ms |
98304 KB |
Output is correct |
7 |
Correct |
92 ms |
98292 KB |
Output is correct |
8 |
Correct |
88 ms |
98376 KB |
Output is correct |
9 |
Correct |
90 ms |
98300 KB |
Output is correct |
10 |
Correct |
94 ms |
98292 KB |
Output is correct |
11 |
Correct |
90 ms |
98296 KB |
Output is correct |
12 |
Correct |
90 ms |
98380 KB |
Output is correct |
13 |
Correct |
96 ms |
98324 KB |
Output is correct |
14 |
Correct |
95 ms |
98296 KB |
Output is correct |
15 |
Correct |
89 ms |
98296 KB |
Output is correct |
16 |
Correct |
86 ms |
98292 KB |
Output is correct |
17 |
Correct |
89 ms |
98280 KB |
Output is correct |
18 |
Correct |
90 ms |
98364 KB |
Output is correct |
19 |
Correct |
92 ms |
98340 KB |
Output is correct |
20 |
Correct |
87 ms |
98404 KB |
Output is correct |