# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
91877 |
2018-12-30T22:16:28 Z |
KLPP |
Rail (IOI14_rail) |
C++14 |
|
94 ms |
764 KB |
#include <bits/stdc++.h>
#include "rail.h"
using namespace std;
void findLocation(int N, int first, int location[], int stype[])
{
int n=N;
for(int i=0;i<n;i++){
location[i]=-1;
stype[i]=-1;
}
location[0]=first;
stype[0]=1;
int dist0[n];
dist0[0]=0;
for(int i=1;i<n;i++){
dist0[i]=getDistance(0,i);
}
int m=1;
for(int i=1;i<n;i++){
if(dist0[i]<dist0[m])m=i;
}
int distm[n];
for(int i=0;i<n;i++){
if(i==m)distm[i]=0;
else{
distm[i]=getDistance(m,i);
}
}
stype[m]=2;
location[m]=location[0]+dist0[m];
vector<pair<int,int> > vleft;
vector<pair<int,int> >vright;
for(int i=0;i<n;i++){
if(i==0){
vleft.push_back(pair<int,int>(distm[i],i));
}
else if(i==m){
vright.push_back(pair<int,int>(dist0[i],i));
}
else if(dist0[i]==distm[i]+dist0[m]){
vleft.push_back(pair<int,int>(distm[i],i));
}else{
vright.push_back(pair<int,int>(dist0[i],i));
}
}
sort(vleft.begin(),vleft.end());
sort(vright.begin(),vright.end());
vector<int> C;
for(int i=0;i<vleft.size();i++){
//cout<<vleft[i].first<<" "<<vleft[i].second<<endl;
if(C.size()==0){
C.push_back(vleft[i].second);
location[vleft[i].second]=location[m]-vleft[i].first;
stype[vleft[i].second]=1;
}else if(stype[vleft[i].second]==-1){
int d=getDistance(vleft[i].second,C[C.size()-1]);
int posC=location[m]-vleft[i].first;
int posD=location[C[C.size()-1]]+d;
int lo,hi;
lo=-1;
hi=C.size();
while(hi-lo>1){
int mid=(hi+lo)/2;
if(location[C[mid]]>posD){
lo=mid;
}else hi=mid;
}//cout<<C[C.size()-1]<<endl;
//cout<<hi<<" "<<C[hi]<<" "<<posD<<" "<<d<<endl;
if(posD+location[m]-2*location[C[hi]]==vleft[i].first){
location[vleft[i].second]=posD;
stype[vleft[i].second]=2;
}else{
C.push_back(vleft[i].second);
location[vleft[i].second]=posC;
stype[vleft[i].second]=1;
}
}else{//cout<<"A"<<endl;
//cout<<stype[vleft[i].second]<<endl;
if(stype[vleft[i].second]==1){//cout<<vleft[i].second<<endl;
C.push_back(vleft[i].second);
}
}
/*cout<<"vect:"<<endl;
for(int j=0;j<C.size();j++)cout<<C[j]<<" ";
cout<<endl;*/
}
vector<int> D;
for(int i=0;i<vright.size();i++){
//cout<<vright[i].first<<" A "<<vright[i].second<<endl;
if(D.size()==0){
D.push_back(vright[i].second);
location[vright[i].second]=location[0]+vright[i].first;
stype[vright[i].second]=2;
}else if(stype[vright[i].second]==-1){
int d=getDistance(vright[i].second,D[D.size()-1]);
int posD=location[0]+vright[i].first;
int posC=location[D[D.size()-1]]-d;
int lo,hi;
lo=-1;
hi=D.size();
while(hi-lo>1){
int mid=(hi+lo)/2;
if(location[D[mid]]<posC){
lo=mid;
}else hi=mid;
}//cout<<C[C.size()-1]<<endl;
//cout<<hi<<" "<<D[hi]<<" "<<posC<<" "<<d<<endl;
if(posC+location[0]-2*location[D[hi]]==-vright[i].first){
location[vright[i].second]=posC;
stype[vright[i].second]=1;
}else{
D.push_back(vright[i].second);
location[vright[i].second]=posD;
stype[vright[i].second]=2;
}
}else{//cout<<"A"<<endl;
//cout<<stype[vleft[i].second]<<endl;
if(stype[vright[i].second]==2){//cout<<vleft[i].second<<endl;
D.push_back(vright[i].second);
}
}
/*for(int j=0;j<D.size();j++)cout<<D[j]<<" ";
cout<<endl;*/
}
/*for(int i=0;i<n;i++){
cout<<stype[i]<<" "<<location[i]<<endl;
}*/
}
Compilation message
rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:54:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<vleft.size();i++){
~^~~~~~~~~~~~~
rail.cpp:94:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<vright.size();i++){
~^~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
256 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
380 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
504 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
380 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
380 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
78 ms |
632 KB |
Output is correct |
2 |
Correct |
83 ms |
668 KB |
Output is correct |
3 |
Correct |
74 ms |
760 KB |
Output is correct |
4 |
Correct |
86 ms |
632 KB |
Output is correct |
5 |
Correct |
87 ms |
632 KB |
Output is correct |
6 |
Correct |
78 ms |
604 KB |
Output is correct |
7 |
Correct |
81 ms |
632 KB |
Output is correct |
8 |
Correct |
87 ms |
632 KB |
Output is correct |
9 |
Correct |
76 ms |
760 KB |
Output is correct |
10 |
Correct |
94 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
80 ms |
688 KB |
Output is correct |
2 |
Correct |
87 ms |
636 KB |
Output is correct |
3 |
Correct |
79 ms |
632 KB |
Output is correct |
4 |
Correct |
74 ms |
632 KB |
Output is correct |
5 |
Correct |
86 ms |
636 KB |
Output is correct |
6 |
Correct |
84 ms |
632 KB |
Output is correct |
7 |
Correct |
85 ms |
548 KB |
Output is correct |
8 |
Correct |
86 ms |
632 KB |
Output is correct |
9 |
Correct |
74 ms |
672 KB |
Output is correct |
10 |
Correct |
76 ms |
764 KB |
Output is correct |
11 |
Correct |
79 ms |
644 KB |
Output is correct |
12 |
Correct |
82 ms |
632 KB |
Output is correct |
13 |
Correct |
84 ms |
760 KB |
Output is correct |
14 |
Correct |
73 ms |
640 KB |
Output is correct |
15 |
Correct |
75 ms |
604 KB |
Output is correct |
16 |
Correct |
71 ms |
632 KB |
Output is correct |
17 |
Correct |
79 ms |
632 KB |
Output is correct |
18 |
Correct |
73 ms |
636 KB |
Output is correct |
19 |
Correct |
79 ms |
760 KB |
Output is correct |
20 |
Correct |
75 ms |
632 KB |
Output is correct |