| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 835246 |
2023-08-23T11:03:00 Z |
HollaFoil |
Rail (IOI14_rail) |
C++14 |
|
61 ms |
34636 KB |
#include <bits/stdc++.h>
#include "rail.h"
using namespace std;
#define maxN 10002
// Distance from house 0;
vector<int> sorted;
int L;
int R;
int locations[maxN];
int types[maxN];
int d[maxN][maxN];
int f;
int s;
int sIndex;
set<int> CLocs;
set<int> DLocs;
int guess = -1;
bool cmp(int i, int j) {
return d[0][i] < d[0][j];
}
// Case 1:
// L ? T R
// ( ( ) )
bool test1(int index) {
guess = locations[R] - d[index][R];
if (guess < 0) return false;
int intermediateForL = guess + (d[L][index] - (guess - locations[L]))/2;
if (DLocs.find(intermediateForL) == DLocs.end()) return false;
int intermediateForFirst = guess + (d[0][index] - (guess - f))/2;
if (DLocs.find(intermediateForFirst) == DLocs.end()) return false;
return true;
}
// Case 2:
// ? L T R
// ( ( ) )
bool test2(int index) {
guess = locations[R] - d[index][R];
if (guess < 0) return false;
int intermediateForL = guess + (d[L][index] - (guess - locations[L]))/2;
if (DLocs.find(intermediateForL) == DLocs.end()) return false;
int intermediateForFirst = guess + (d[0][index] - (guess - f))/2;
if (DLocs.find(intermediateForFirst) == DLocs.end()) return false;
return true;
}
// Case 3:
// L T ? R
// ( ( ) )
bool test3(int index) {
guess = locations[L] + d[index][L];
int intermediateForR = guess + (d[R][index] - (locations[R] - guess))/2;
if (CLocs.find(intermediateForR) == DLocs.end()) return false;
if (guess > f) {
if (d[0][index] != guess-f) return false;
}
else {
d[sIndex][index] = d[index][sIndex] = d[0][index] - d[0][sIndex];
int intermediateForSecond = guess + (d[sIndex][index] - (s - guess))/2;
if (CLocs.find(intermediateForSecond) == CLocs.end()) return false;
}
return true;
}
// Case 4:
// L T R ?
// ( ( ) )
bool test4(int index) {
guess = locations[L] + d[index][L];
if (guess > 1000000) return false;
int intermediateForR = guess + (d[R][index] - (locations[R] - guess))/2;
if (CLocs.find(intermediateForR) == DLocs.end()) return false;
if (guess > f) {
if (d[0][index] != guess-f) return false;
}
else {
d[sIndex][index] = d[index][sIndex] = d[0][index] - d[0][sIndex];
int intermediateForSecond = guess + (d[sIndex][index] - (s - guess))/2;
if (CLocs.find(intermediateForSecond) == CLocs.end()) return false;
}
return true;
}
void findLocation(int N, int first, int location[], int stype[]) {
for (int i = 1; i < N; i++) {
d[0][i] = d[i][0] = getDistance(0, i);
sorted.push_back(i);
}
sort(sorted.begin(), sorted.end(), cmp);
int index = sorted[0];
L = 0;
R = index;
locations[0] = first;
locations[index] = first + d[0][index];
types[0] = 1;
types[index] = 2;
CLocs.insert(first);
DLocs.insert(locations[index]);
f = first;
s = locations[index];
sIndex = index;
for (int i = 1; i < sorted.size(); i++) {
index = sorted[i];
d[L][index] = d[index][L] = getDistance(L, index);
d[R][index] = d[index][R] = getDistance(R, index);
if (test1(index)) {
locations[index] = guess;
types[index] = 1;
}
else if (test2(index)) {
locations[index] = guess;
types[index] = 1;
}
else if (test3(index)) {
locations[index] = guess;
types[index] = 2;
}
else if (test4(index)) {
locations[index] = guess;
types[index] = 2;
}
if (locations[index] > locations[R]) R = index;
if (locations[index] < locations[L]) L = index;
}
for (int i = 0; i < N; i++) {
location[i] = locations[i];
stype[i] = types[i];
}
}
/*
Track left most (, right most ).
Sort from stop 0 by distance (stop 0 is '(');
Have to discern 4 cases. Let T be
a potential intermediary turn stop
Case 1:
L ? T R
( ( ) )
If we have d[?][R] be a one way trip,
then d[?][] = d[L][T] + d[T][?], and
T must be a node we have seen
Case 2:
? L T R
( ( ) )
If we have d[?][R] be a one way trip,
then d[?][] = d[L][T] + d[T][?], and
T must be a node we have seen
Case 3:
L T ? R
( ( ) )
Case 4:
L T R ?
( ( ) )
2 6
1 5
1 3
1 1
2 7
2 9
2 11
*/
Compilation message
rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:109:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
109 | for (int i = 1; i < sorted.size(); i++) {
| ~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
724 KB |
Output is correct |
| 2 |
Correct |
1 ms |
724 KB |
Output is correct |
| 3 |
Correct |
1 ms |
724 KB |
Output is correct |
| 4 |
Correct |
1 ms |
724 KB |
Output is correct |
| 5 |
Correct |
1 ms |
724 KB |
Output is correct |
| 6 |
Correct |
1 ms |
724 KB |
Output is correct |
| 7 |
Correct |
1 ms |
724 KB |
Output is correct |
| 8 |
Correct |
1 ms |
724 KB |
Output is correct |
| 9 |
Correct |
1 ms |
724 KB |
Output is correct |
| 10 |
Correct |
1 ms |
724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
724 KB |
Output is correct |
| 2 |
Correct |
1 ms |
724 KB |
Output is correct |
| 3 |
Correct |
1 ms |
724 KB |
Output is correct |
| 4 |
Correct |
1 ms |
848 KB |
Output is correct |
| 5 |
Correct |
1 ms |
724 KB |
Output is correct |
| 6 |
Correct |
1 ms |
724 KB |
Output is correct |
| 7 |
Correct |
1 ms |
724 KB |
Output is correct |
| 8 |
Correct |
1 ms |
724 KB |
Output is correct |
| 9 |
Correct |
1 ms |
724 KB |
Output is correct |
| 10 |
Correct |
0 ms |
724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
61 ms |
34636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
59 ms |
34636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
