# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
294996 |
2020-09-09T11:51:35 Z |
mieszko11b |
Rail (IOI14_rail) |
C++14 |
|
1561 ms |
1912 KB |
#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
using ii = pair<int, int>;
#define X first
#define Y second
map<ii, int> M;
int dist(int a, int b) {
if(a > b) swap(a, b);
if(M.count({a, b}))
return M[{a, b}];
return M[{a, b}] = getDistance(a, b);
}
void findLocation(int N, int first, int location[], int stype[]) {
for(int i = 0 ; i < N ; i++)
stype[i] = location[i] = 0;
stype[0] = 1;
location[0] = first;
int b = 1;
for(int i = 2 ; i < N ; i++)
if(dist(0, i) < dist(0, b))
b = i;
stype[b] = 2;
location[b] = location[0] + dist(0, b);
vector<int> lst;
lst.push_back(b);
int fst = 0;
vector<ii> cand;
for(int i = 0 ; i < N ; i++) {
if(i == 0 || i == b)
continue;
int d0 = dist(0, i);
int db = dist(b, i);
int d = dist(0, b);
if(d0 - db == d) {
if(db < d)
cand.push_back({d0, i});
} else
cand.push_back({d0, i});
}
sort(cand.begin(), cand.end());
for(auto p : cand) {
int d = dist(0, lst.back());
int w = p.Y;
int dlst = dist(lst.back(), w);
bool ins = true;
if(dlst >= d)
ins = false;
else {
int ind = 0;
while(dist(lst[ind], 0) < d - dlst)
ind++;
if(dist(lst[ind], 0) == d - dlst)
ins = false;
else {
if(dist(0, lst[ind]) + (dist(0, lst[ind]) + dlst - d) != dist(0, w))
ins = false;
}
}
if(ins) {
stype[w] = 1;
location[w] = location[lst.back()] - dlst;
} else {
stype[w] = 2;
location[w] = location[0] + dist(0, w);
lst.push_back(w);
}
}
int a = 0;
for(int i = 1 ; i < N ; i++)
if(i != b)
if(dist(b, i) < dist(b, a))
a = i;
stype[a] = 1;
location[a] = location[b] - dist(b, a);
fst = b;
lst.clear();
lst.push_back(a);
cand.clear();
for(int i = 0 ; i < N ; i++) {
if(stype[i])
continue;
cand.push_back({dist(fst, i), i});
}
sort(cand.begin(), cand.end());
for(auto p : cand) {
int d = dist(fst, lst.back());
int w = p.Y;
int dlst = dist(lst.back(), w);
bool ins = true;
if(dlst >= d)
ins = false;
else {
int ind = 0;
while(dist(lst[ind], fst) < d - dlst)
ind++;
if(dist(lst[ind], fst) == d - dlst)
ins = false;
else {
if(dist(fst, lst[ind]) + (dist(fst, lst[ind]) + dlst - d) != dist(fst, w))
ins = false;
}
}
if(ins) {
stype[w] = 2;
location[w] = location[lst.back()] + dlst;
} else {
stype[w] = 1;
location[w] = location[fst] - dist(fst, w);
lst.push_back(w);
}
}
//~ for(int i = 0 ; i < N ; i++)
//~ cout << stype[i] << " " << location[i] << endl;
//~ cout << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
436 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
2 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1076 ms |
1788 KB |
Output is correct |
2 |
Correct |
889 ms |
1784 KB |
Output is correct |
3 |
Correct |
1012 ms |
1656 KB |
Output is correct |
4 |
Correct |
809 ms |
1668 KB |
Output is correct |
5 |
Correct |
1178 ms |
1912 KB |
Output is correct |
6 |
Correct |
1561 ms |
1600 KB |
Output is correct |
7 |
Correct |
1062 ms |
1528 KB |
Output is correct |
8 |
Correct |
864 ms |
1528 KB |
Output is correct |
9 |
Correct |
879 ms |
1656 KB |
Output is correct |
10 |
Correct |
891 ms |
1528 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1092 ms |
1528 KB |
Output is correct |
2 |
Correct |
904 ms |
1568 KB |
Output is correct |
3 |
Correct |
871 ms |
1556 KB |
Output is correct |
4 |
Correct |
800 ms |
1656 KB |
Output is correct |
5 |
Correct |
1186 ms |
1528 KB |
Output is correct |
6 |
Correct |
1559 ms |
1576 KB |
Output is correct |
7 |
Correct |
1109 ms |
1528 KB |
Output is correct |
8 |
Correct |
853 ms |
1664 KB |
Output is correct |
9 |
Correct |
846 ms |
1528 KB |
Output is correct |
10 |
Correct |
890 ms |
1528 KB |
Output is correct |
11 |
Correct |
1176 ms |
1508 KB |
Output is correct |
12 |
Correct |
1250 ms |
1508 KB |
Output is correct |
13 |
Correct |
991 ms |
1648 KB |
Output is correct |
14 |
Correct |
1201 ms |
1524 KB |
Output is correct |
15 |
Correct |
882 ms |
1656 KB |
Output is correct |
16 |
Correct |
921 ms |
1528 KB |
Output is correct |
17 |
Correct |
1312 ms |
1632 KB |
Output is correct |
18 |
Correct |
1204 ms |
1536 KB |
Output is correct |
19 |
Correct |
915 ms |
1656 KB |
Output is correct |
20 |
Correct |
1142 ms |
1664 KB |
Output is correct |