| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 282605 |
2020-08-24T15:37:00 Z |
amoo_safar |
Rail (IOI14_rail) |
C++17 |
|
99 ms |
768 KB |
#include "rail.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 5010;
int d0[N];
int d1[N];
void findLocation(int n, int fst, int loc[], int sty[]){
for(int i = 1; i < n; i++)
d0[i] = getDistance(0, i);
int mn = 1;
for(int i = 2; i < n; i++)
if(d0[i] < d0[mn])
mn = i;
//cerr << "mn : " << mn << '\n';
d1[0] = d0[mn];
for(int i = 1; i < n; i++)
d1[i] = getDistance(mn, i);
int L = d0[mn];
loc[0] = fst; sty[0] = 1;
loc[mn] = fst + L; sty[mn] = 2;
vector<int> A, B, C;
for(int i = 1; i < n; i++){
if(i == mn) continue;
if(d0[i] == d1[i] + L){
if(d1[i] < L) B.pb(i);
else A.pb(i);
} else {
C.pb(i);
}
}
for(auto x : B){
sty[x] = 1;
loc[x] = loc[0] + L - d1[x];
}
/*
cerr << "A : ";
for(auto x : A) cerr << x << ' ';
cerr << '\n';
cerr << "B : ";
for(auto x : B) cerr << x << ' ';
cerr << '\n';
cerr << "C : ";
for(auto x : C) cerr << x << ' ';
cerr << '\n';
*/
sort(A.begin(), A.end(), [&](int i, int j){
return d1[i] < d1[j];
});
vector<int> V;
int sz, ds, la;
if(!A.empty()){
la = A[0];
loc[la] = loc[mn] - d1[la];
V.pb(la);
sty[la] = 1;
sz = A.size();
for(int i = 1; i < sz; i++){
ds = getDistance(la, A[i]);
int pos = loc[la] + ds;
bool flg = false;
for(auto x : V){
if(loc[x] <= pos){
if(d1[A[i]] == abs(loc[x] - pos) + d1[x]) flg = true;
break;
}
}
if(flg){
loc[A[i]] = pos;
sty[A[i]] = 2;
} else {
loc[A[i]] = loc[mn] - d1[A[i]];
sty[A[i]] = 1;
la = A[i];
V.pb(la);
}
}
}
sort(C.begin(), C.end(), [&](int i, int j){
return d0[i] < d0[j];
});
if(!C.empty()){
V.clear();
la = C[0];
loc[la] = loc[0] + d0[la];
V.pb(la);
sty[la] = 2;
sz = C.size();
for(int i = 1; i < sz; i++){
ds = getDistance(la, C[i]);
int pos = loc[la] - ds;
bool flg = false;
for(auto x : V){
if(loc[x] >= pos){
if(d0[C[i]] == abs(loc[x] - pos) + d0[x]) flg = true;
break;
}
}
if(flg){
loc[C[i]] = pos;
sty[C[i]] = 1;
} else {
loc[C[i]] = loc[0] + d0[C[i]];
sty[C[i]] = 2;
la = C[i];
V.pb(la);
}
}
}
/*
cerr << "sty : ";
for(int i = 0; i < n; i++) cerr << sty[i] << ' ';
cerr << '\n';
*/
}
/*
1
4
1 1
2 4
2 7
2 9
2
6
1 3
2 6
2 7
1 1
1 0
2 8
*/
| # |
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 |
372 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 |
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 |
372 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 |
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 |
89 ms |
512 KB |
Output is correct |
| 2 |
Correct |
92 ms |
632 KB |
Output is correct |
| 3 |
Correct |
89 ms |
760 KB |
Output is correct |
| 4 |
Correct |
89 ms |
632 KB |
Output is correct |
| 5 |
Correct |
90 ms |
760 KB |
Output is correct |
| 6 |
Correct |
91 ms |
760 KB |
Output is correct |
| 7 |
Correct |
94 ms |
632 KB |
Output is correct |
| 8 |
Correct |
87 ms |
768 KB |
Output is correct |
| 9 |
Correct |
88 ms |
632 KB |
Output is correct |
| 10 |
Correct |
88 ms |
632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
88 ms |
632 KB |
Output is correct |
| 2 |
Correct |
88 ms |
632 KB |
Output is correct |
| 3 |
Correct |
87 ms |
632 KB |
Output is correct |
| 4 |
Correct |
87 ms |
636 KB |
Output is correct |
| 5 |
Correct |
91 ms |
632 KB |
Output is correct |
| 6 |
Correct |
92 ms |
632 KB |
Output is correct |
| 7 |
Correct |
89 ms |
632 KB |
Output is correct |
| 8 |
Correct |
89 ms |
632 KB |
Output is correct |
| 9 |
Correct |
90 ms |
632 KB |
Output is correct |
| 10 |
Correct |
89 ms |
632 KB |
Output is correct |
| 11 |
Correct |
87 ms |
632 KB |
Output is correct |
| 12 |
Correct |
90 ms |
644 KB |
Output is correct |
| 13 |
Correct |
92 ms |
632 KB |
Output is correct |
| 14 |
Correct |
96 ms |
632 KB |
Output is correct |
| 15 |
Correct |
99 ms |
632 KB |
Output is correct |
| 16 |
Correct |
96 ms |
760 KB |
Output is correct |
| 17 |
Correct |
91 ms |
632 KB |
Output is correct |
| 18 |
Correct |
90 ms |
632 KB |
Output is correct |
| 19 |
Correct |
88 ms |
632 KB |
Output is correct |
| 20 |
Correct |
91 ms |
648 KB |
Output is correct |
