# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
730295 | 2023-04-25T15:18:57 Z | ogibogi2004 | Rail (IOI14_rail) | C++14 | 90 ms | 772 KB |
#include "rail.h" #include<bits/stdc++.h> using namespace std; void findLocation(int N, int first, int location[], int stype[]) { memset(stype,0,sizeof(stype)); memset(location,0,sizeof(location)); location[0]=first; stype[0]=1; map<int,int> mtype; mtype[location[0]]=1; vector<pair<int,int> >distances; vector<int>dist0(N); vector<int>dist1(N); for(int i=1;i<N;i++) { distances.push_back({getDistance(0, i),i}); dist0[i]=distances.back().first; } sort(distances.begin(),distances.end()); location[distances[0].second]=location[0]+distances[0].first; stype[distances[0].second]=2; mtype[location[distances[0].second]]=2; set<int>cs; set<int>ds; int minc=0,maxd=distances[0].second,sec=maxd; cs.insert(location[0]); ds.insert(location[distances[0].second]); for(int i=1;i<N;i++) { if(i==maxd)continue; dist1[i]=getDistance(maxd,i); } for(int i=1;i<distances.size();i++) { int j=distances[i].second; if(dist0[j]==dist1[j]+dist0[sec]) { //left of sec if(dist1[j]<dist0[sec]) { //between 0 and sec location[j]=location[sec]-dist1[j]; stype[j]=1; mtype[location[j]]=1; } else { //left of 0 //can be C or D //if D, there should be C before it //C X 0 D //calc dist(minc,X) => if dist(minc,X)+location[sec]-location[minc]==dist1[minc], ok, it is D int t=getDistance(minc,j); int pos1=(t+location[sec]-dist1[j]+location[minc])/2; if(mtype[pos1]!=1) { stype[j]=1; location[j]=location[sec]-dist1[j]; minc=j; mtype[location[j]]=1; } else { stype[j]=2; location[j]=location[minc]+t; mtype[location[j]]=2; } } } else { //cout<<j<<" ?2\n"; //right of sec //0 D X D //if X=C, then getDist(maxd,X)+location[maxd]-location[0]=dist0[X] int t=getDistance(j, maxd); int pos1=(-t+location[0]+dist0[j]+location[maxd])/2; //7- //cout<<pos1<<" "<<(-t+location[0]+dist0[j]+location[maxd])<<endl; if(mtype[pos1]!=2) { stype[j]=2; location[j]=location[0]+dist0[j]; maxd=j; mtype[location[j]]=2; } else { stype[j]=1; location[j]=location[maxd]-t; mtype[location[j]]=1; } } } /*for(int i=0;i<N;i++) { cout<<i<<": "<<location[i]<<" "<<stype[i]<<endl; }*/ }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 340 KB | Output is correct |
3 | Correct | 0 ms | 340 KB | Output is correct |
4 | Correct | 1 ms | 340 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 | 340 KB | Output is correct |
8 | Correct | 1 ms | 268 KB | Output is correct |
9 | Correct | 0 ms | 340 KB | Output is correct |
10 | Correct | 0 ms | 340 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 340 KB | Output is correct |
3 | Correct | 1 ms | 340 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 1 ms | 340 KB | Output is correct |
6 | Correct | 1 ms | 340 KB | Output is correct |
7 | Correct | 0 ms | 340 KB | Output is correct |
8 | Correct | 1 ms | 352 KB | Output is correct |
9 | Correct | 1 ms | 340 KB | Output is correct |
10 | Correct | 1 ms | 340 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 70 ms | 712 KB | Output is correct |
2 | Correct | 69 ms | 716 KB | Output is correct |
3 | Correct | 72 ms | 772 KB | Output is correct |
4 | Correct | 72 ms | 756 KB | Output is correct |
5 | Correct | 79 ms | 716 KB | Output is correct |
6 | Correct | 74 ms | 756 KB | Output is correct |
7 | Correct | 69 ms | 768 KB | Output is correct |
8 | Correct | 80 ms | 716 KB | Output is correct |
9 | Correct | 84 ms | 756 KB | Output is correct |
10 | Correct | 73 ms | 716 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 69 ms | 724 KB | Output is correct |
2 | Correct | 74 ms | 768 KB | Output is correct |
3 | Correct | 67 ms | 760 KB | Output is correct |
4 | Correct | 69 ms | 756 KB | Output is correct |
5 | Correct | 72 ms | 752 KB | Output is correct |
6 | Correct | 73 ms | 772 KB | Output is correct |
7 | Correct | 76 ms | 752 KB | Output is correct |
8 | Correct | 70 ms | 756 KB | Output is correct |
9 | Correct | 77 ms | 752 KB | Output is correct |
10 | Correct | 81 ms | 756 KB | Output is correct |
11 | Correct | 73 ms | 772 KB | Output is correct |
12 | Correct | 70 ms | 768 KB | Output is correct |
13 | Correct | 69 ms | 772 KB | Output is correct |
14 | Correct | 78 ms | 764 KB | Output is correct |
15 | Correct | 90 ms | 756 KB | Output is correct |
16 | Correct | 76 ms | 716 KB | Output is correct |
17 | Correct | 76 ms | 764 KB | Output is correct |
18 | Correct | 73 ms | 760 KB | Output is correct |
19 | Correct | 82 ms | 768 KB | Output is correct |
20 | Correct | 75 ms | 772 KB | Output is correct |