# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
349242 |
2021-01-17T08:10:53 Z |
tengiz05 |
Rail (IOI14_rail) |
C++17 |
|
89 ms |
4588 KB |
#include "rail.h"
#ifndef EVAL
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define pii pair<int,int>
#define ff first
#define ss second
const int MAXN = 5005, MM = 1e6+5;
int d0[MAXN], d1[MAXN], n;
int Type[MM];
void findLocation(int N, int first, int location[], int stype[]){
n = N;
for(int i=1;i<n;i++)d0[i] = getDistance(0,i);
stype[0]=1;
location[0]=first;
Type[first] = 1;
if(n == 1)return;
int cherez, mn = 1e9;
for(int i=1;i<n;i++){
if(mn > d0[i]){
mn = d0[i];
cherez = i;
}
}
stype[cherez]=2;
location[cherez] = d0[cherez]+first;
Type[location[cherez]] = 2;
vector<pii> left, right;
for(int i=0;i<n;i++){
if(i != cherez){
d1[i] = getDistance(cherez, i);
}
}
for(int i=1;i<n;i++){
if(i != cherez){
if(d0[i] == d0[cherez] + d1[i]){
if(d0[cherez] > d1[i]){
stype[i] = 1;
location[i] = location[cherez] - d1[i];
Type[location[i]] = 1;
}else left.push_back({d1[i],i});
}
else right.push_back({d0[i],i});
}
}
sort(all(left));
sort(all(right));
int L = 0;
for(auto [dist, i] : left){
int t = getDistance(L, i);
int gap = (d1[L] + t - d1[i])/2;
if(Type[location[L] + gap] == 1){
location[i] = location[L]+t;
stype[i] = 2;
Type[location[i]] = 2;
}else {
location[i] = location[cherez] - d1[i];
stype[i] = 1;
Type[location[i]] = 1;
L = i;
}
}
int R = cherez;
for(auto [dist, i] : right){
int t = getDistance(R, i);
int gap = (d0[R] + t - d0[i])/2;
if(Type[location[R] - gap] == 2){
location[i] = location[R]-t;
stype[i] = 1;
Type[location[i]] = 1;
}else {
location[i] = location[0] + d0[i];
stype[i] = 2;
Type[location[i]] = 2;
R = i;
}
}
return;
}
Compilation message
rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:38:3: warning: 'cherez' may be used uninitialized in this function [-Wmaybe-uninitialized]
38 | if(i != cherez){
| ^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
86 ms |
4204 KB |
Output is correct |
2 |
Correct |
87 ms |
4332 KB |
Output is correct |
3 |
Correct |
89 ms |
4460 KB |
Output is correct |
4 |
Correct |
87 ms |
4460 KB |
Output is correct |
5 |
Correct |
85 ms |
4332 KB |
Output is correct |
6 |
Correct |
86 ms |
4204 KB |
Output is correct |
7 |
Correct |
87 ms |
4204 KB |
Output is correct |
8 |
Correct |
87 ms |
4460 KB |
Output is correct |
9 |
Correct |
87 ms |
4352 KB |
Output is correct |
10 |
Correct |
86 ms |
4460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
86 ms |
4204 KB |
Output is correct |
2 |
Correct |
88 ms |
4480 KB |
Output is correct |
3 |
Correct |
85 ms |
4460 KB |
Output is correct |
4 |
Correct |
86 ms |
4332 KB |
Output is correct |
5 |
Correct |
87 ms |
4332 KB |
Output is correct |
6 |
Correct |
86 ms |
4204 KB |
Output is correct |
7 |
Correct |
88 ms |
4204 KB |
Output is correct |
8 |
Correct |
87 ms |
4460 KB |
Output is correct |
9 |
Correct |
89 ms |
4332 KB |
Output is correct |
10 |
Correct |
87 ms |
4460 KB |
Output is correct |
11 |
Correct |
86 ms |
4204 KB |
Output is correct |
12 |
Correct |
86 ms |
4332 KB |
Output is correct |
13 |
Correct |
86 ms |
4332 KB |
Output is correct |
14 |
Correct |
86 ms |
4332 KB |
Output is correct |
15 |
Correct |
86 ms |
4372 KB |
Output is correct |
16 |
Correct |
88 ms |
4588 KB |
Output is correct |
17 |
Correct |
86 ms |
4460 KB |
Output is correct |
18 |
Correct |
88 ms |
4332 KB |
Output is correct |
19 |
Correct |
86 ms |
4332 KB |
Output is correct |
20 |
Correct |
86 ms |
4460 KB |
Output is correct |