# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
15779 |
2015-07-25T16:48:12 Z |
gs13068 |
Rail (IOI14_rail) |
C++ |
|
232 ms |
844 KB |
#include "rail.h"
#include<algorithm>
std::pair<int,int> a[5555];
int c[5555];
int d[5555];
void findLocation(int n,int fir,int loc[],int stp[])
{
int i,j,k,l,sec,le,ri,t;
loc[0]=fir;
stp[0]=1;
fir=0;
for(i=1;i<n;i++)
{
c[i]=getDistance(fir,i);
a[i].first=c[i];
a[i].second=i;
}
sec=std::min_element(a+1,a+n)->second;
loc[sec]=loc[fir]+c[sec];
stp[sec]=2;
for(i=1;i<n;i++)
{
d[i]=getDistance(sec,i);
a[i].first=std::min(c[i],d[i]);
}
std::sort(a+1,a+n);
le=fir;
ri=sec;
for(i=2;i<n;i++)
{
j=a[i].second;
if(c[j]==d[j]+c[sec])
{
t=getDistance(le,j);
l=-1;
for(k=0;k<i;k++)if(stp[a[k].second]==1&&loc[a[k].second]<loc[le]+t&&(l==-1||loc[a[k].second]>loc[l]))l=a[k].second;
if(l>=0&&d[j]==loc[sec]-loc[l]+loc[le]+t-loc[l])
{
loc[j]=loc[le]+t;
stp[j]=2;
}
else
{
loc[j]=loc[sec]-d[j];
stp[j]=1;
if(loc[j]<loc[le])le=j;
}
}
else
{
t=getDistance(ri,j);
l=-1;
for(k=0;k<i;k++)if(stp[a[k].second]==2&&loc[a[k].second]>loc[ri]-t&&(l==-1||loc[a[k].second]<loc[l]))l=a[k].second;
if(l>=0&&c[j]==loc[l]-loc[fir]+loc[l]-loc[ri]+t)
{
loc[j]=loc[ri]-t;
stp[j]=1;
}
else
{
loc[j]=loc[fir]+c[j];
stp[j]=2;
if(loc[j]>loc[ri])ri=j;
}
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
416 KB |
Output is correct |
4 |
Correct |
3 ms |
416 KB |
Output is correct |
5 |
Correct |
2 ms |
596 KB |
Output is correct |
6 |
Correct |
3 ms |
596 KB |
Output is correct |
7 |
Correct |
3 ms |
596 KB |
Output is correct |
8 |
Correct |
2 ms |
596 KB |
Output is correct |
9 |
Correct |
2 ms |
596 KB |
Output is correct |
10 |
Correct |
2 ms |
616 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
616 KB |
Output is correct |
2 |
Correct |
2 ms |
616 KB |
Output is correct |
3 |
Correct |
3 ms |
616 KB |
Output is correct |
4 |
Correct |
3 ms |
616 KB |
Output is correct |
5 |
Correct |
2 ms |
616 KB |
Output is correct |
6 |
Correct |
2 ms |
636 KB |
Output is correct |
7 |
Correct |
2 ms |
636 KB |
Output is correct |
8 |
Correct |
2 ms |
636 KB |
Output is correct |
9 |
Correct |
2 ms |
636 KB |
Output is correct |
10 |
Correct |
2 ms |
636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
145 ms |
844 KB |
Output is correct |
2 |
Correct |
166 ms |
844 KB |
Output is correct |
3 |
Correct |
167 ms |
844 KB |
Output is correct |
4 |
Correct |
177 ms |
844 KB |
Output is correct |
5 |
Correct |
167 ms |
844 KB |
Output is correct |
6 |
Correct |
187 ms |
844 KB |
Output is correct |
7 |
Correct |
176 ms |
844 KB |
Output is correct |
8 |
Correct |
152 ms |
844 KB |
Output is correct |
9 |
Correct |
149 ms |
844 KB |
Output is correct |
10 |
Correct |
157 ms |
844 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
139 ms |
844 KB |
Output is correct |
2 |
Correct |
150 ms |
844 KB |
Output is correct |
3 |
Correct |
156 ms |
844 KB |
Output is correct |
4 |
Correct |
156 ms |
844 KB |
Output is correct |
5 |
Correct |
205 ms |
844 KB |
Output is correct |
6 |
Correct |
186 ms |
844 KB |
Output is correct |
7 |
Correct |
175 ms |
844 KB |
Output is correct |
8 |
Correct |
167 ms |
844 KB |
Output is correct |
9 |
Correct |
167 ms |
844 KB |
Output is correct |
10 |
Correct |
167 ms |
844 KB |
Output is correct |
11 |
Correct |
232 ms |
844 KB |
Output is correct |
12 |
Correct |
175 ms |
844 KB |
Output is correct |
13 |
Correct |
153 ms |
844 KB |
Output is correct |
14 |
Correct |
148 ms |
844 KB |
Output is correct |
15 |
Correct |
180 ms |
844 KB |
Output is correct |
16 |
Correct |
156 ms |
844 KB |
Output is correct |
17 |
Correct |
179 ms |
844 KB |
Output is correct |
18 |
Correct |
143 ms |
844 KB |
Output is correct |
19 |
Correct |
179 ms |
844 KB |
Output is correct |
20 |
Correct |
180 ms |
844 KB |
Output is correct |