# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
30930 |
2017-08-01T07:05:46 Z |
kajebiii |
Rail (IOI14_rail) |
C++14 |
|
146 ms |
4688 KB |
#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<double, double> pd;
typedef pair<int, int> pi;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll; typedef pair<ll, pi> plp;
typedef tuple<int, int, int> ti; typedef tuple<ll, int, int> tli;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF * 2;
const int MAX_N = 5e3 + 100, MAX_M = 1e6 + 100;
int N, Fi, Se, Dix, Lo[MAX_N], Type[MAX_M];
int D[2][MAX_N];
void record(int ix, int lo, int ty) {
Lo[ix] = lo;
Type[lo] = ty;
}
void recordAuto(int fr, int to, int d) {
if(Type[Lo[fr]] == 1) record(to, Lo[fr] + d, 2);
else record(to, Lo[fr] - d, 1);
}
void findLocation(int n, int fi, int location[], int stype[]) {
N = n; Fi = fi;
record(0, fi, 1);
int fminV = INF;
for(int i=0; i<N; i++) {
if(i == 0) continue;
D[0][i] = getDistance(0, i);
if(fminV > D[0][i]) {
fminV = D[0][i];
Dix = i;
}
}
Se = Fi + fminV;
recordAuto(0, Dix, fminV);
vector<int> ls, rs;
for(int i=0; i<N; i++) {
if(i == 0 || i == Dix) continue;
D[1][i] = getDistance(Dix, i);
if(D[0][i] == D[1][i] + D[0][Dix]) {
if(D[1][i] < D[0][Dix]) {
record(i, Lo[Dix] - D[1][i], 1);
}else{
ls.push_back(i);
}
}else rs.push_back(i);
}
sort(ALL(ls), [&](int a, int b) {return D[1][a] < D[1][b];});
sort(ALL(rs), [&](int a, int b) {return D[1][a] < D[1][b];});
int nowC = 0, loC = Fi;
for(int ix : ls) {
int x = Se - D[1][ix];
int d = getDistance(nowC, ix);
int rest = loC - x;
if(Type[loC + (d - rest) / 2] == 1) {
recordAuto(nowC, ix, d);
}else{
recordAuto(Dix, ix, D[1][ix]);
nowC = ix;
loC = Lo[ix];
}
}
int nowD = Dix, loD = Se;
for(int ix : rs) {
int x = Fi + D[0][ix];
int d = getDistance(nowD, ix);
int rest = x - loD;
if(Type[loD - (d - rest) / 2] == 2) {
recordAuto(nowD, ix, d);
}else{
recordAuto(0, ix, D[0][ix]);
nowD = ix;
loD = Lo[ix];
}
}
for(int i=0; i<N; i++) {
location[i] = Lo[i];
stype[i] = Type[Lo[i]];
}
return;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
416 KB |
Output is correct |
4 |
Correct |
2 ms |
416 KB |
Output is correct |
5 |
Correct |
3 ms |
472 KB |
Output is correct |
6 |
Correct |
2 ms |
472 KB |
Output is correct |
7 |
Correct |
2 ms |
516 KB |
Output is correct |
8 |
Correct |
2 ms |
644 KB |
Output is correct |
9 |
Correct |
2 ms |
668 KB |
Output is correct |
10 |
Correct |
2 ms |
668 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
668 KB |
Output is correct |
2 |
Correct |
2 ms |
668 KB |
Output is correct |
3 |
Correct |
2 ms |
668 KB |
Output is correct |
4 |
Correct |
2 ms |
672 KB |
Output is correct |
5 |
Correct |
2 ms |
672 KB |
Output is correct |
6 |
Correct |
2 ms |
672 KB |
Output is correct |
7 |
Correct |
2 ms |
672 KB |
Output is correct |
8 |
Correct |
2 ms |
672 KB |
Output is correct |
9 |
Correct |
2 ms |
672 KB |
Output is correct |
10 |
Correct |
2 ms |
672 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
90 ms |
4424 KB |
Output is correct |
2 |
Correct |
96 ms |
4424 KB |
Output is correct |
3 |
Correct |
91 ms |
4588 KB |
Output is correct |
4 |
Correct |
92 ms |
4588 KB |
Output is correct |
5 |
Correct |
109 ms |
4588 KB |
Output is correct |
6 |
Correct |
94 ms |
4588 KB |
Output is correct |
7 |
Correct |
104 ms |
4588 KB |
Output is correct |
8 |
Correct |
95 ms |
4588 KB |
Output is correct |
9 |
Correct |
90 ms |
4588 KB |
Output is correct |
10 |
Correct |
93 ms |
4588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
104 ms |
4588 KB |
Output is correct |
2 |
Correct |
94 ms |
4588 KB |
Output is correct |
3 |
Correct |
97 ms |
4688 KB |
Output is correct |
4 |
Correct |
92 ms |
4688 KB |
Output is correct |
5 |
Correct |
94 ms |
4688 KB |
Output is correct |
6 |
Correct |
99 ms |
4688 KB |
Output is correct |
7 |
Correct |
87 ms |
4688 KB |
Output is correct |
8 |
Correct |
88 ms |
4688 KB |
Output is correct |
9 |
Correct |
88 ms |
4688 KB |
Output is correct |
10 |
Correct |
97 ms |
4688 KB |
Output is correct |
11 |
Correct |
102 ms |
4688 KB |
Output is correct |
12 |
Correct |
94 ms |
4688 KB |
Output is correct |
13 |
Correct |
146 ms |
4688 KB |
Output is correct |
14 |
Correct |
92 ms |
4688 KB |
Output is correct |
15 |
Correct |
91 ms |
4688 KB |
Output is correct |
16 |
Correct |
95 ms |
4688 KB |
Output is correct |
17 |
Correct |
97 ms |
4688 KB |
Output is correct |
18 |
Correct |
87 ms |
4688 KB |
Output is correct |
19 |
Correct |
86 ms |
4688 KB |
Output is correct |
20 |
Correct |
96 ms |
4688 KB |
Output is correct |