# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
587920 | 2022-07-02T14:08:00 Z | yutabi | Rail (IOI14_rail) | C++14 | 79 ms | 4372 KB |
#include "rail.h" #include <bits/stdc++.h> using namespace std; #define pb push_back typedef pair <int,int> ii; int left_index=0; int left_location; int left_diff[5000]; int right_index; int right_location; int right_diff[5000]; vector <ii> left_vals; vector <ii> right_vals; int types[1000007]; void findLocation(int N, int first, int location[], int stype[]) { left_location=first; int mini=300000000; for(int i=0;i<N;i++) { if(left_index!=i) { left_diff[i]=getDistance(left_index,i); if(left_diff[i]<mini) { right_index=i; right_location=left_location+left_diff[i]; mini=left_diff[i]; } } } types[left_location]=1; location[left_index]=left_location; stype[left_index]=1; types[right_location]=2; location[right_index]=right_location; stype[right_index]=2; for(int i=0;i<N;i++) { if(right_index!=i) { right_diff[i]=getDistance(right_index,i); } } for(int i=0;i<N;i++) { if(i!=left_index && i!=right_index) { if(right_diff[i]+right_diff[left_index]==left_diff[i]) { if(right_diff[i]<right_diff[left_index]) { location[i]=right_location-right_diff[i]; stype[i]=1; types[right_location-right_diff[i]]=1; } else { left_vals.pb(ii(right_diff[i],i)); } } else { right_vals.pb(ii(left_diff[i],i)); } } } sort(left_vals.begin(),left_vals.end()); int leftest_C=-1; for(int i=0;i<left_vals.size();i++) { if(leftest_C==-1) { leftest_C=left_vals[i].second; location[left_vals[i].second]=right_location-left_vals[i].first; stype[left_vals[i].second]=1; types[right_location-left_vals[i].first]=1; continue; } int res=getDistance(left_vals[i].second,leftest_C); if(res==left_vals[i].first+right_diff[leftest_C]) { leftest_C=left_vals[i].second; location[left_vals[i].second]=right_location-left_vals[i].first; stype[left_vals[i].second]=1; types[right_location-right_diff[left_vals[i].second]]=1; continue; } if(types[location[leftest_C]+(res-(left_vals[i].first-right_diff[leftest_C]))/2]==1) { location[left_vals[i].second]=location[leftest_C]+res; stype[left_vals[i].second]=2; types[location[leftest_C]+res]=2; } else { leftest_C=left_vals[i].second; location[left_vals[i].second]=right_location-left_vals[i].first; stype[left_vals[i].second]=1; types[right_location-right_diff[left_vals[i].second]]=1; continue; } } sort(right_vals.begin(),right_vals.end()); int rightest_D=-1; for(int i=0;i<right_vals.size();i++) { if(rightest_D==-1) { rightest_D=right_vals[i].second; location[right_vals[i].second]=left_location+right_vals[i].first; stype[right_vals[i].second]=2; types[left_location+right_vals[i].first]=2; continue; } int res=getDistance(right_vals[i].second,rightest_D); if(res==right_vals[i].first+left_diff[rightest_D]) { rightest_D=right_vals[i].second; location[right_vals[i].second]=left_location+right_vals[i].first; stype[right_vals[i].second]=2; types[left_location+right_vals[i].first]=2; continue; } if(types[location[rightest_D]-(res-(right_vals[i].first-left_diff[rightest_D]))/2]==2) { location[right_vals[i].second]=location[rightest_D]-res; stype[right_vals[i].second]=1; types[location[rightest_D]+res]=1; } else { rightest_D=right_vals[i].second; location[right_vals[i].second]=left_location+right_vals[i].first; stype[right_vals[i].second]=2; types[left_location+right_vals[i].first]=2; continue; } } return; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 352 KB | Output is correct |
2 | Correct | 1 ms | 388 KB | Output is correct |
3 | Correct | 1 ms | 340 KB | Output is correct |
4 | Correct | 0 ms | 468 KB | Output is correct |
5 | Correct | 0 ms | 388 KB | Output is correct |
6 | Correct | 1 ms | 340 KB | Output is correct |
7 | Correct | 1 ms | 340 KB | Output is correct |
8 | Correct | 0 ms | 340 KB | Output is correct |
9 | Correct | 0 ms | 340 KB | Output is correct |
10 | Correct | 1 ms | 340 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 388 KB | Output is correct |
2 | Correct | 0 ms | 388 KB | Output is correct |
3 | Correct | 1 ms | 340 KB | Output is correct |
4 | Correct | 1 ms | 384 KB | Output is correct |
5 | Correct | 1 ms | 340 KB | Output is correct |
6 | Correct | 1 ms | 340 KB | Output is correct |
7 | Correct | 1 ms | 392 KB | Output is correct |
8 | Correct | 1 ms | 340 KB | Output is correct |
9 | Correct | 1 ms | 384 KB | Output is correct |
10 | Correct | 1 ms | 340 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 68 ms | 4172 KB | Output is correct |
2 | Correct | 67 ms | 4228 KB | Output is correct |
3 | Correct | 79 ms | 4368 KB | Output is correct |
4 | Correct | 72 ms | 4348 KB | Output is correct |
5 | Correct | 65 ms | 4300 KB | Output is correct |
6 | Correct | 68 ms | 4108 KB | Output is correct |
7 | Correct | 66 ms | 4092 KB | Output is correct |
8 | Correct | 70 ms | 4236 KB | Output is correct |
9 | Correct | 78 ms | 4224 KB | Output is correct |
10 | Correct | 71 ms | 4352 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 67 ms | 4108 KB | Output is correct |
2 | Correct | 67 ms | 4228 KB | Output is correct |
3 | Correct | 65 ms | 4352 KB | Output is correct |
4 | Correct | 69 ms | 4352 KB | Output is correct |
5 | Correct | 68 ms | 4220 KB | Output is correct |
6 | Correct | 66 ms | 4172 KB | Output is correct |
7 | Correct | 67 ms | 4108 KB | Output is correct |
8 | Correct | 65 ms | 4228 KB | Output is correct |
9 | Correct | 68 ms | 4220 KB | Output is correct |
10 | Correct | 67 ms | 4372 KB | Output is correct |
11 | Correct | 69 ms | 4108 KB | Output is correct |
12 | Correct | 66 ms | 4300 KB | Output is correct |
13 | Correct | 69 ms | 4228 KB | Output is correct |
14 | Correct | 70 ms | 4232 KB | Output is correct |
15 | Correct | 69 ms | 4220 KB | Output is correct |
16 | Correct | 66 ms | 4356 KB | Output is correct |
17 | Correct | 67 ms | 4352 KB | Output is correct |
18 | Correct | 74 ms | 4220 KB | Output is correct |
19 | Correct | 66 ms | 4236 KB | Output is correct |
20 | Correct | 67 ms | 4348 KB | Output is correct |