# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
348930 | 2021-01-16T05:56:36 Z | beksultan04 | Rail (IOI14_rail) | C++14 | 116 ms | 748 KB |
#include "rail.h" #include <bits/stdc++.h> //#include "grader.cpp" using namespace std; int d0[5001], d1[5001]; void findLocation(int N, int first, int l[], int s[]) { for(int i = 0 ; i < N; i++){ l[i]=-1; s[i]=-1; } int len = 2e9, ind ; vector <pair <int, int> > left, right; for (int i = 1; i < N; i++){ d0[i] = getDistance(0, i); if(d0[i] < len ){ len = d0[i]; ind = i; } } l[0]=first; s[0] = 1; l[ind] = first + len; s[ind] = 2; for (int i = 0; i < N; i++){ if( ind !=i){ d1[i] = getDistance( ind, i); } } for (int i = 1; i < N; i++){ if(i != ind){ if( d0[i] == len + d1[i]){ if(len > d1[i]){ l[i] = l[ind] - d1[i]; s[i]=1; } else{ left.push_back( make_pair (d1[i], i)); } } else right.push_back( make_pair (d0[i], i)); } } sort(left.begin() , left.end()); sort(right.begin() , right.end()); int R = ind; for(int i = 0 ; i < right.size();i++){ int ds = getDistance( R , right[i].second); int gap = ( d0[R] + ds - d0[right[i].second] )/ 2; bool flag = true; for(int j = 0; j < N; j++){ if( l[R] - gap == l[j] && s[j] == 2){ flag = 0; l[right[i].second] = l[R] - ds; s[right[i].second] = 1; break; } } if(flag){ l[right[i].second] = first + d0[right[i].second]; s[right[i].second] = 2; R = right[i].second; } } R = 0; for(int i = 0 ; i < left.size();i++){ int ds = getDistance( R , left[i].second); int gap = ( d1[R] + ds - d1[left[i].second] )/ 2; bool flag = true; for(int j = 0; j < N; j++){ if( l[R] + gap == l[j] && s[j] == 1){ flag = 0; l[left[i].second] = l[R] + ds; s[left[i].second] = 2; break; } } if(flag){ l[left[i].second] = l[ind] - d1[left[i].second]; s[left[i].second] = 1; R = left[i].second; } } return; }
Compilation message
# | 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 | 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 | 512 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 | 99 ms | 656 KB | Output is correct |
2 | Correct | 95 ms | 620 KB | Output is correct |
3 | Correct | 95 ms | 640 KB | Output is correct |
4 | Correct | 97 ms | 748 KB | Output is correct |
5 | Correct | 94 ms | 620 KB | Output is correct |
6 | Correct | 106 ms | 748 KB | Output is correct |
7 | Correct | 105 ms | 620 KB | Output is correct |
8 | Correct | 93 ms | 748 KB | Output is correct |
9 | Correct | 94 ms | 620 KB | Output is correct |
10 | Correct | 96 ms | 748 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 98 ms | 620 KB | Output is correct |
2 | Correct | 102 ms | 688 KB | Output is correct |
3 | Correct | 93 ms | 620 KB | Output is correct |
4 | Correct | 98 ms | 620 KB | Output is correct |
5 | Correct | 115 ms | 656 KB | Output is correct |
6 | Correct | 96 ms | 620 KB | Output is correct |
7 | Correct | 98 ms | 668 KB | Output is correct |
8 | Correct | 97 ms | 596 KB | Output is correct |
9 | Correct | 98 ms | 748 KB | Output is correct |
10 | Correct | 102 ms | 620 KB | Output is correct |
11 | Correct | 96 ms | 620 KB | Output is correct |
12 | Correct | 102 ms | 620 KB | Output is correct |
13 | Correct | 96 ms | 688 KB | Output is correct |
14 | Correct | 108 ms | 656 KB | Output is correct |
15 | Correct | 116 ms | 748 KB | Output is correct |
16 | Correct | 94 ms | 656 KB | Output is correct |
17 | Correct | 94 ms | 748 KB | Output is correct |
18 | Correct | 94 ms | 748 KB | Output is correct |
19 | Correct | 95 ms | 740 KB | Output is correct |
20 | Correct | 109 ms | 668 KB | Output is correct |