This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "rail.h"
#include<bits/stdc++.h>
using namespace std;
void findLocation(int N, int first, int location[], int stype[])
{
location[0]=first;
stype[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;
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;
}
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);
if(t+location[sec]-location[minc]==dist1[minc])
{
stype[j]=2;
location[j]=location[minc]+t;
}
else
{
stype[j]=1;
location[j]=location[sec]-dist1[j];
minc=j;
}
}
}
else
{
//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);
if(t+location[maxd]-location[0]==dist0[j])
{
stype[j]=1;
location[j]=location[maxd]-t;
}
else
{
stype[j]=2;
location[j]=location[0]+dist0[j];
maxd=j;
}
}
}
/*for(int i=0;i<N;i++)
{
cout<<i<<": "<<location[i]<<" "<<stype[i]<<endl;
}*/
}
Compilation message (stderr)
rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:30:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for(int i=1;i<distances.size();i++)
| ~^~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |