# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
588233 |
2022-07-02T20:33:05 Z |
FatihSolak |
Rail (IOI14_rail) |
C++17 |
|
98 ms |
32076 KB |
#include "rail.h"
#include <bits/stdc++.h>
#define N 5005
using namespace std;
int d[N][N];
int get(int i,int j){
if(i > j)swap(i,j);
if(i == j)return 0;
if(d[i][j])
return d[i][j];
return d[i][j] = getDistance(i,j);
}
void findLocation(int n, int first, int location[], int stype[])
{
for(int i = 0;i<n;i++){
location[i] = -1;
stype[i] = -1;
}
location[0] = first;
stype[0] = 1;
if(n == 1)return;
vector<pair<int,int>> v;
for(int i = 0;i<n;i++){
if(i == 0)continue;
v.push_back({get(0,i),i});
}
sort(v.begin(),v.end());
int last = v[0].second;
int x = last;
location[v[0].second] = get(0,v[0].second) + first;
stype[v[0].second] = 2;
set<int> points = {location[last]};
for(int i = 1;i<v.size();i++){
//cout << v[i].second << endl;
if(get(0,v[i].second) > 2*get(0,x) && get(0,v[i].second) > get(x,v[i].second) + get(0,x) - 2)
continue;
int nwpoint = location[last] - get(last, v[i].second);
int rval = *points.lower_bound(nwpoint);
//cout << nwpoint << " " << rval << endl;
if(2*rval - nwpoint - first == get(0,v[i].second)){
location[v[i].second] = nwpoint;
stype[v[i].second] = 1;
}
else{
location[v[i].second] = get(0,v[i].second) + first;
stype[v[i].second] = 2;
last = v[i].second;
points.insert(location[last]);
}
}
vector<pair<int,int>> nw;
for(auto u:v){
if(stype[u.second] == -1)
nw.push_back(u);
}
v = nw;
// cout << endl;
// for(int i = 0;i<n;i++){
// cout << stype[i] << " " << location[i] << endl;
// }
// cout << endl;
if(v.empty())return;
int frst = v[0].second;
int y = 0;
location[v[0].second] = first - (get(0,v[0].second) - 2*get(0,x));
stype[v[0].second] = 1;
points = {location[frst]};
for(int i = 1;i<v.size();i++){
// cout << i << " x " << v[i].second << endl;
// for(auto u:points){
// cout << u << " ";
// }
// cout << endl;
int nwpoint = get(frst, v[i].second) + location[frst];
int lval = *prev(points.upper_bound(nwpoint));
// cout << nwpoint << " " << lval << endl;
// cout << get(0,v[i].second) << endl;
if(-2*lval + nwpoint + 2*location[x] -first == get(0,v[i].second)){
location[v[i].second] = nwpoint;
stype[v[i].second] = 2;
}
else{
location[v[i].second] = first - (get(0,v[i].second) - 2*get(0,x)) ;
stype[v[i].second] = 1;
frst = v[i].second;
points.insert(location[frst]);
}
}
// for(int i = 0;i<n;i++){
// cout << stype[i] << " " << location[i] << endl;
// }
// cout << endl;
}
Compilation message
rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:33:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | for(int i = 1;i<v.size();i++){
| ~^~~~~~~~~
rail.cpp:68:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for(int i = 1;i<v.size();i++){
| ~^~~~~~~~~
rail.cpp:64:9: warning: unused variable 'y' [-Wunused-variable]
64 | int y = 0;
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
596 KB |
Output is correct |
2 |
Correct |
1 ms |
724 KB |
Output is correct |
3 |
Correct |
1 ms |
596 KB |
Output is correct |
4 |
Correct |
1 ms |
596 KB |
Output is correct |
5 |
Correct |
1 ms |
596 KB |
Output is correct |
6 |
Correct |
1 ms |
596 KB |
Output is correct |
7 |
Correct |
1 ms |
596 KB |
Output is correct |
8 |
Correct |
1 ms |
596 KB |
Output is correct |
9 |
Correct |
1 ms |
596 KB |
Output is correct |
10 |
Correct |
1 ms |
724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
596 KB |
Output is correct |
2 |
Correct |
1 ms |
596 KB |
Output is correct |
3 |
Correct |
1 ms |
596 KB |
Output is correct |
4 |
Correct |
1 ms |
596 KB |
Output is correct |
5 |
Correct |
0 ms |
596 KB |
Output is correct |
6 |
Correct |
1 ms |
660 KB |
Output is correct |
7 |
Correct |
1 ms |
596 KB |
Output is correct |
8 |
Correct |
1 ms |
596 KB |
Output is correct |
9 |
Correct |
1 ms |
596 KB |
Output is correct |
10 |
Correct |
1 ms |
724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
93 ms |
20056 KB |
Output is correct |
2 |
Correct |
79 ms |
18816 KB |
Output is correct |
3 |
Correct |
78 ms |
22388 KB |
Output is correct |
4 |
Correct |
79 ms |
20868 KB |
Output is correct |
5 |
Correct |
78 ms |
22144 KB |
Output is correct |
6 |
Correct |
81 ms |
24304 KB |
Output is correct |
7 |
Correct |
87 ms |
28412 KB |
Output is correct |
8 |
Correct |
85 ms |
30324 KB |
Output is correct |
9 |
Correct |
78 ms |
19332 KB |
Output is correct |
10 |
Correct |
89 ms |
32076 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
81 ms |
20044 KB |
Output is correct |
2 |
Correct |
83 ms |
18824 KB |
Output is correct |
3 |
Correct |
80 ms |
22392 KB |
Output is correct |
4 |
Correct |
78 ms |
20864 KB |
Output is correct |
5 |
Correct |
80 ms |
22120 KB |
Output is correct |
6 |
Correct |
87 ms |
24184 KB |
Output is correct |
7 |
Correct |
98 ms |
28492 KB |
Output is correct |
8 |
Correct |
93 ms |
30340 KB |
Output is correct |
9 |
Correct |
78 ms |
19320 KB |
Output is correct |
10 |
Correct |
85 ms |
31972 KB |
Output is correct |
11 |
Correct |
85 ms |
29428 KB |
Output is correct |
12 |
Correct |
87 ms |
20312 KB |
Output is correct |
13 |
Correct |
88 ms |
26744 KB |
Output is correct |
14 |
Correct |
79 ms |
23032 KB |
Output is correct |
15 |
Correct |
82 ms |
25848 KB |
Output is correct |
16 |
Correct |
80 ms |
24056 KB |
Output is correct |
17 |
Correct |
79 ms |
23160 KB |
Output is correct |
18 |
Correct |
90 ms |
28284 KB |
Output is correct |
19 |
Correct |
83 ms |
27468 KB |
Output is correct |
20 |
Correct |
80 ms |
18580 KB |
Output is correct |