# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
12713 |
2015-01-01T16:27:43 Z |
ainta |
Rail (IOI14_rail) |
C++ |
|
126 ms |
4684 KB |
#include "rail.h"
#include<algorithm>
using namespace std;
#define MAX_M 1000010
int D1[5010], D2[5010];
int loc[5010];
int typ2[MAX_M];
int CL, CR;
struct AA{
int dis, num;
bool operator<(const AA &p)const{
return dis < p.dis;
}
}L[5010], R[5010];
void Add(int p, int a, int b){
loc[p] = a;
typ2[a] = b;
}
void Do(int p, int a, int d){
if (typ2[loc[a]] == 1)Add(p, loc[a] + d, 2);
else Add(p, loc[a] - d, 1);
}
void findLocation(int N, int first, int location[], int stype[])
{
int i, MM = MAX_M, x, pv, d, t, k, j;
Add(0, first, 1);
for (i = 1; i < N; i++){
D1[i] = getDistance(0, i);
if (MM > D1[i]){
MM = D1[i];
x = i;
}
}
Do(x, 0, D1[x]);
for (i = 1; i < N; i++){
if (i == x)continue;
D2[i] = getDistance(x, i);
if (D1[i] == D2[i] + D1[x]){
if (D2[i] < D1[x]){
Do(i, x, D2[i]);
}
else{
L[CL].dis = D2[i], L[CL].num = i;
CL++;
}
}
else{
R[CR].dis = D2[i], R[CR].num = i;
CR++;
}
}
sort(L, L + CL);
sort(R, R + CR);
pv = 0;
for (i = 0; i < CL; i++){
k = L[i].num;
t = loc[x] - D2[k];
d = getDistance(pv, k);
if (d % 2 != (loc[pv] - t) % 2 || typ2[loc[pv] + (d - (loc[pv] - t)) / 2] == 1)Do(k, pv, d);
else{
Do(k, x, D2[k]);
pv = k;
}
}
pv = x;
for (i = 0; i < CR; i++){
k = R[i].num;
t = loc[0] + D1[k];
d = getDistance(pv, k);
if (d % 2 != (t - loc[pv]) % 2 || typ2[loc[pv] - (d - (t - loc[pv])) / 2] == 2)Do(k, pv, d);
else{
Do(k, 0, D1[k]);
pv = k;
}
}
for (i = 0; i < N; i++)location[i] = loc[i], stype[i] = typ2[loc[i]];
}
Compilation message
rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:31:37: warning: unused variable 'j' [-Wunused-variable]
int i, MM = MAX_M, x, pv, d, t, k, j;
^
rail.cpp:40:4: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
Do(x, 0, D1[x]);
~~^~~~~~~~~~~~~
# |
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 |
436 KB |
Output is correct |
4 |
Correct |
2 ms |
508 KB |
Output is correct |
5 |
Correct |
2 ms |
584 KB |
Output is correct |
6 |
Correct |
2 ms |
584 KB |
Output is correct |
7 |
Correct |
4 ms |
588 KB |
Output is correct |
8 |
Correct |
2 ms |
588 KB |
Output is correct |
9 |
Correct |
2 ms |
744 KB |
Output is correct |
10 |
Correct |
2 ms |
744 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
744 KB |
Output is correct |
2 |
Correct |
2 ms |
744 KB |
Output is correct |
3 |
Correct |
2 ms |
744 KB |
Output is correct |
4 |
Correct |
1 ms |
744 KB |
Output is correct |
5 |
Correct |
2 ms |
744 KB |
Output is correct |
6 |
Correct |
2 ms |
744 KB |
Output is correct |
7 |
Correct |
3 ms |
744 KB |
Output is correct |
8 |
Correct |
2 ms |
744 KB |
Output is correct |
9 |
Correct |
2 ms |
744 KB |
Output is correct |
10 |
Correct |
5 ms |
744 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
95 ms |
4428 KB |
Output is correct |
2 |
Correct |
97 ms |
4432 KB |
Output is correct |
3 |
Correct |
87 ms |
4684 KB |
Output is correct |
4 |
Correct |
89 ms |
4684 KB |
Output is correct |
5 |
Correct |
93 ms |
4684 KB |
Output is correct |
6 |
Correct |
88 ms |
4684 KB |
Output is correct |
7 |
Correct |
92 ms |
4684 KB |
Output is correct |
8 |
Correct |
92 ms |
4684 KB |
Output is correct |
9 |
Correct |
87 ms |
4684 KB |
Output is correct |
10 |
Correct |
92 ms |
4684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
98 ms |
4684 KB |
Output is correct |
2 |
Correct |
92 ms |
4684 KB |
Output is correct |
3 |
Correct |
107 ms |
4684 KB |
Output is correct |
4 |
Correct |
95 ms |
4684 KB |
Output is correct |
5 |
Correct |
98 ms |
4684 KB |
Output is correct |
6 |
Correct |
95 ms |
4684 KB |
Output is correct |
7 |
Correct |
96 ms |
4684 KB |
Output is correct |
8 |
Correct |
102 ms |
4684 KB |
Output is correct |
9 |
Correct |
118 ms |
4684 KB |
Output is correct |
10 |
Correct |
105 ms |
4684 KB |
Output is correct |
11 |
Correct |
126 ms |
4684 KB |
Output is correct |
12 |
Correct |
104 ms |
4684 KB |
Output is correct |
13 |
Correct |
95 ms |
4684 KB |
Output is correct |
14 |
Correct |
96 ms |
4684 KB |
Output is correct |
15 |
Correct |
92 ms |
4684 KB |
Output is correct |
16 |
Correct |
102 ms |
4684 KB |
Output is correct |
17 |
Correct |
92 ms |
4684 KB |
Output is correct |
18 |
Correct |
93 ms |
4684 KB |
Output is correct |
19 |
Correct |
94 ms |
4684 KB |
Output is correct |
20 |
Correct |
94 ms |
4684 KB |
Output is correct |