# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
246591 |
2020-07-09T16:40:34 Z |
faremy |
Rail (IOI14_rail) |
C++14 |
|
115 ms |
632 KB |
#include "rail.h"
#include <algorithm>
#include <vector>
const int MAXN = 5e3;
int dist0[MAXN];
int distA[MAXN];
std::vector<int> left, right;
void findLocation(int N, int first, int location[], int stype[])
{
location[0] = first;
stype[0] = 1;
for (int iSta = 1; iSta < N; iSta++)
dist0[iSta] = getDistance(0, iSta);
int stationA = std::min_element(dist0 + 1, dist0 + N) - dist0;
location[stationA] = location[0] + dist0[stationA];
stype[stationA] = 2;
distA[0] = dist0[stationA];
for (int iSta = 1; iSta < N; iSta++)
if (iSta != stationA)
{
distA[iSta] = getDistance(stationA, iSta);
if (dist0[iSta] == dist0[stationA] + distA[iSta])
left.emplace_back(iSta);
else
right.emplace_back(iSta);
}
std::sort(right.begin(), right.end(), [](int a, int b) { return (dist0[a] < dist0[b]); });
int lastD = -1;
for (int iSta = 0; iSta < (int)right.size(); iSta++)
{
int station = right[iSta];
location[station] = location[0] + dist0[station];
stype[station] = 2;
if (lastD != -1)
{
int distLast = getDistance(lastD, station);
for (int jSta = 0; jSta < iSta; jSta++)
{
int stat2 = right[jSta];
if (stype[stat2] == 2 && distLast - (location[lastD] - location[stat2]) == dist0[station] - (location[stat2] - location[0]))
{
location[station] = location[stat2] - dist0[station] + (location[stat2] - location[0]);
stype[station] = 1;
break;
}
}
}
if (stype[station] == 2)
lastD = station;
}
std::sort(left.begin(), left.end(), [](int a, int b) { return (distA[a] < distA[b]); });
int lastC = -1;
for (int iSta = 0; iSta < (int)left.size(); iSta++)
{
int station = left[iSta];
location[station] = location[stationA] - distA[station];
stype[station] = 1;
if (lastC != -1)
{
int distLast = getDistance(lastC, station);
for (int jSta = 0; jSta < iSta; jSta++)
{
int stat2 = left[jSta];
if (stype[stat2] == 1 && distLast - (location[stat2] - location[lastC]) == distA[station] - (location[stationA] - location[stat2]))
{
location[station] = location[stat2] + distA[station] - (location[stationA] - location[stat2]);
stype[station] = 2;
break;
}
}
}
if (stype[station] == 1)
lastC = station;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
4 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
4 ms |
384 KB |
Output is correct |
10 |
Correct |
4 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
4 ms |
256 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
4 ms |
384 KB |
Output is correct |
6 |
Correct |
4 ms |
256 KB |
Output is correct |
7 |
Correct |
4 ms |
384 KB |
Output is correct |
8 |
Correct |
4 ms |
384 KB |
Output is correct |
9 |
Correct |
4 ms |
384 KB |
Output is correct |
10 |
Correct |
4 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
96 ms |
504 KB |
Output is correct |
2 |
Correct |
94 ms |
632 KB |
Output is correct |
3 |
Correct |
97 ms |
632 KB |
Output is correct |
4 |
Correct |
91 ms |
504 KB |
Output is correct |
5 |
Correct |
101 ms |
632 KB |
Output is correct |
6 |
Correct |
112 ms |
632 KB |
Output is correct |
7 |
Correct |
102 ms |
492 KB |
Output is correct |
8 |
Correct |
95 ms |
504 KB |
Output is correct |
9 |
Correct |
96 ms |
504 KB |
Output is correct |
10 |
Correct |
97 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
99 ms |
504 KB |
Output is correct |
2 |
Correct |
97 ms |
504 KB |
Output is correct |
3 |
Correct |
97 ms |
632 KB |
Output is correct |
4 |
Correct |
97 ms |
632 KB |
Output is correct |
5 |
Correct |
104 ms |
508 KB |
Output is correct |
6 |
Correct |
109 ms |
620 KB |
Output is correct |
7 |
Correct |
103 ms |
508 KB |
Output is correct |
8 |
Correct |
96 ms |
632 KB |
Output is correct |
9 |
Correct |
92 ms |
504 KB |
Output is correct |
10 |
Correct |
96 ms |
504 KB |
Output is correct |
11 |
Correct |
115 ms |
504 KB |
Output is correct |
12 |
Correct |
106 ms |
504 KB |
Output is correct |
13 |
Correct |
103 ms |
504 KB |
Output is correct |
14 |
Correct |
101 ms |
508 KB |
Output is correct |
15 |
Correct |
95 ms |
504 KB |
Output is correct |
16 |
Correct |
97 ms |
504 KB |
Output is correct |
17 |
Correct |
107 ms |
632 KB |
Output is correct |
18 |
Correct |
100 ms |
504 KB |
Output is correct |
19 |
Correct |
97 ms |
504 KB |
Output is correct |
20 |
Correct |
103 ms |
504 KB |
Output is correct |