# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
8577 |
2014-09-17T11:07:12 Z |
cki86201 |
Rail (IOI14_rail) |
C++ |
|
354 ms |
968 KB |
#include "rail.h"
#include<algorithm>
using namespace std;
typedef pair<int,int> Pi;
#define X first
#define Y second
int F[5050], T[5050];
Pi tF[5050], tT[5050];
int tf, tt;
int st[5050], top;
int val[5050];
void findLocation(int N, int first, int location[], int stype[])
{
location[0] = first, stype[0] = 1;
int i, tar = 1;
for(i=1;i<N;i++){
F[i] = getDistance(0, i);
if(F[tar] > F[i])tar = i;
}
location[tar] = F[tar] + first;
stype[tar] = 2;
for(i=1;i<N;i++)if(i != tar)T[i] = getDistance(tar, i);
for(i=1;i<N;i++){
if(i == tar)continue;
if(F[i] == T[i] + F[tar])tT[tt++] = Pi(T[i], i);
else tF[tf++] = Pi(F[i] - F[tar], i);
}
sort(tT, tT+tt);
sort(tF, tF+tf);
if(tt)val[tT[0].Y] = tT[0].X, stype[tT[0].Y] = 1;
st[top++] = tT[0].Y;
for(i=1;i<tt;i++){
int t = getDistance(tT[i].Y, st[top-1]), j;
for(j=0;j<top;j++){
int b = val[st[j]]*2 - tT[i].X;
if(val[st[top-1]]-b == t)break;
}
if(j == top){
val[tT[i].Y] = tT[i].X, stype[tT[i].Y] = 1;
st[top++] = tT[i].Y;
}
else{
val[tT[i].Y] = val[st[j]]*2 - tT[i].X, stype[tT[i].Y] = 2;
}
}
for(i=0;i<tt;i++)location[tT[i].Y] = location[tar] - val[tT[i].Y];
top = 0;
if(tf)val[tF[0].Y] = tF[0].X, stype[tF[0].Y] = 2;
st[top++] = tF[0].Y;
for(i=1;i<tf;i++){
int t = getDistance(tF[i].Y, st[top-1]), j;
for(j=0;j<top;j++){
int b = val[st[j]]*2 - tF[i].X;
if(val[st[top-1]]-b == t)break;
}
if(j == top){
val[tF[i].Y] = tF[i].X, stype[tF[i].Y] = 2;
st[top++] = tF[i].Y;
}
else{
val[tF[i].Y] = val[st[j]]*2 - tF[i].X, stype[tF[i].Y] = 1;
}
}
for(i=0;i<tf;i++)location[tF[i].Y] = location[tar] + val[tF[i].Y];
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
248 KB |
Output is correct |
2 |
Correct |
2 ms |
356 KB |
Output is correct |
3 |
Correct |
3 ms |
560 KB |
Output is correct |
4 |
Correct |
2 ms |
560 KB |
Output is correct |
5 |
Correct |
3 ms |
560 KB |
Output is correct |
6 |
Correct |
3 ms |
636 KB |
Output is correct |
7 |
Correct |
3 ms |
636 KB |
Output is correct |
8 |
Correct |
2 ms |
636 KB |
Output is correct |
9 |
Correct |
2 ms |
728 KB |
Output is correct |
10 |
Correct |
3 ms |
728 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
728 KB |
Output is correct |
2 |
Correct |
2 ms |
728 KB |
Output is correct |
3 |
Correct |
2 ms |
728 KB |
Output is correct |
4 |
Correct |
2 ms |
728 KB |
Output is correct |
5 |
Correct |
2 ms |
728 KB |
Output is correct |
6 |
Correct |
3 ms |
728 KB |
Output is correct |
7 |
Correct |
2 ms |
728 KB |
Output is correct |
8 |
Correct |
2 ms |
728 KB |
Output is correct |
9 |
Correct |
2 ms |
764 KB |
Output is correct |
10 |
Correct |
2 ms |
764 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
96 ms |
836 KB |
Output is correct |
2 |
Correct |
99 ms |
968 KB |
Output is correct |
3 |
Correct |
96 ms |
968 KB |
Output is correct |
4 |
Correct |
99 ms |
968 KB |
Output is correct |
5 |
Correct |
112 ms |
968 KB |
Output is correct |
6 |
Correct |
94 ms |
968 KB |
Output is correct |
7 |
Correct |
125 ms |
968 KB |
Output is correct |
8 |
Correct |
94 ms |
968 KB |
Output is correct |
9 |
Correct |
117 ms |
968 KB |
Output is correct |
10 |
Correct |
96 ms |
968 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
100 ms |
968 KB |
Output is correct |
2 |
Correct |
96 ms |
968 KB |
Output is correct |
3 |
Correct |
120 ms |
968 KB |
Output is correct |
4 |
Correct |
89 ms |
968 KB |
Output is correct |
5 |
Correct |
354 ms |
968 KB |
Output is correct |
6 |
Correct |
99 ms |
968 KB |
Output is correct |
7 |
Correct |
97 ms |
968 KB |
Output is correct |
8 |
Correct |
97 ms |
968 KB |
Output is correct |
9 |
Correct |
110 ms |
968 KB |
Output is correct |
10 |
Correct |
101 ms |
968 KB |
Output is correct |
11 |
Correct |
109 ms |
968 KB |
Output is correct |
12 |
Correct |
112 ms |
968 KB |
Output is correct |
13 |
Correct |
110 ms |
968 KB |
Output is correct |
14 |
Correct |
103 ms |
968 KB |
Output is correct |
15 |
Correct |
102 ms |
968 KB |
Output is correct |
16 |
Correct |
101 ms |
968 KB |
Output is correct |
17 |
Correct |
97 ms |
968 KB |
Output is correct |
18 |
Correct |
96 ms |
968 KB |
Output is correct |
19 |
Correct |
93 ms |
968 KB |
Output is correct |
20 |
Correct |
98 ms |
968 KB |
Output is correct |