# |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
126776 |
2019-07-08T11:49:04 Z |
anayk |
철로 (IOI14_rail) |
C++14 |
|
170 ms |
712 KB |
#include <algorithm>
#include <iostream>
#include "rail.h"
#define U 1
#define D 0
#define L 0
#define R 1
void findLocation(int N, int first, int location[], int stype[])
{
stype[0] = 1;
location[0] = first;
std::pair<int, int> d[N-1];
for(int i = 1; i < N; i++)
{
d[i-1].first = getDistance(0, i);
d[i-1].second = i;
}
std::sort(d, d+N-1);
int hinge = d[0].second;
int ends[2][2];
for(int i = 0; i < 2; i++)
for(int j = 0; j < 2; j++)
ends[i][j] = -1;
ends[U][L] = ends[U][R] = d[0].second;
ends[D][R] = 0;
location[hinge] = d[0].first + first;
stype[hinge] = 2;
for(int i = 1; i < N-1; i++)
{
int u = d[i].second;
int a = getDistance(u, hinge);
if(a + d[0].first == d[i].first)
{
if(ends[D][L] == -1)
{
ends[D][L] = u;
location[u] = location[hinge] - a;
stype[u] = 1;
if(location[u] > location[ends[D][R]])
ends[D][R] = u;
continue;
}
int b = getDistance(u, ends[D][L]);
int x = location[ends[D][L]] + b;
int y = -1;
int j = 0;
while((location[d[j].second] > x) || (stype[d[j].second] != 1))
{
j++;
}
y = d[j].second;
if(d[j].first + x - location[y] != d[i].first)
{
location[u] = location[hinge] - a;
stype[u] = 1;
ends[D][L] = u;
if(location[u] > location[ends[D][R]])
ends[D][R] = u;
}
else
{
location[u] = location[ends[D][L]] + b;
stype[u] = 2;
if(location[u] < location[ends[U][L]])
ends[U][L] = u;
}
}
else
{
int b = getDistance(u, ends[U][R]);
int x = location[ends[U][R]] - b;
int j = 0;
while(stype[d[j].second] != 2 || location[d[j].second] < x)
j++;
int y = d[j].second;
if(d[j].first + location[y] - x != d[i].first)
{
location[u] = d[i].first + first;
stype[u] = 2;
ends[U][R] = u;
}
else
{
location[u] = location[ends[U][R]] - b;
stype[u] = 1;
if(location[u] > location[ends[D][R]])
ends[D][R] = u;
}
}
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
380 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
380 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
256 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
396 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 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
100 ms |
548 KB |
Output is correct |
2 |
Correct |
112 ms |
588 KB |
Output is correct |
3 |
Correct |
121 ms |
504 KB |
Output is correct |
4 |
Correct |
126 ms |
632 KB |
Output is correct |
5 |
Correct |
163 ms |
632 KB |
Output is correct |
6 |
Correct |
170 ms |
504 KB |
Output is correct |
7 |
Correct |
162 ms |
504 KB |
Output is correct |
8 |
Correct |
126 ms |
544 KB |
Output is correct |
9 |
Correct |
118 ms |
504 KB |
Output is correct |
10 |
Correct |
150 ms |
504 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
99 ms |
540 KB |
Output is correct |
2 |
Correct |
110 ms |
504 KB |
Output is correct |
3 |
Correct |
124 ms |
632 KB |
Output is correct |
4 |
Correct |
126 ms |
504 KB |
Output is correct |
5 |
Correct |
166 ms |
672 KB |
Output is correct |
6 |
Correct |
170 ms |
508 KB |
Output is correct |
7 |
Correct |
164 ms |
584 KB |
Output is correct |
8 |
Correct |
128 ms |
592 KB |
Output is correct |
9 |
Correct |
118 ms |
504 KB |
Output is correct |
10 |
Correct |
149 ms |
632 KB |
Output is correct |
11 |
Correct |
162 ms |
504 KB |
Output is correct |
12 |
Correct |
164 ms |
632 KB |
Output is correct |
13 |
Correct |
114 ms |
632 KB |
Output is correct |
14 |
Correct |
96 ms |
504 KB |
Output is correct |
15 |
Correct |
135 ms |
504 KB |
Output is correct |
16 |
Correct |
112 ms |
504 KB |
Output is correct |
17 |
Correct |
170 ms |
584 KB |
Output is correct |
18 |
Correct |
98 ms |
712 KB |
Output is correct |
19 |
Correct |
152 ms |
504 KB |
Output is correct |
20 |
Correct |
162 ms |
632 KB |
Output is correct |