# |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
747117 |
2023-05-23T16:09:21 Z |
MODDI |
철로 (IOI14_rail) |
C++14 |
|
89 ms |
624 KB |
#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define mp make_pair
#define pb push_back
void findLocation(int N, int first, int location[], int stype[])
{
vector<int> dist0(N);
location[0] = first;stype[0] = 1;
for(int i = 1; i <= N; i++){
int here = getDistance(0, i);
stype[i] = 0;
dist0[i] = here;
}
vi pos(N-1), distp(N);
iota(pos.begin(), pos.end(), 1);
sort(pos.begin(), pos.end(), [&](int a, int b){
return dist0[a] < dist0[b];
});
int p = pos[0];
stype[p] = 2;
location[p] = first + dist0[p];
vi left, right;
for(int u : pos){
if(u != p){
distp[u] = getDistance(p, u);
if(dist0[u] == dist0[p] + distp[u]){
if(distp[u] < dist0[p]){
stype[u] = 1;
location[u] = location[p] - distp[u];
}
else
left.pb(u);
}
else right.pb(u);
}
}
vi up;
for(int u : right){
if(up.empty()){
up.pb(u);
stype[u] = 2;
location[u] = location[0] + dist0[u];
continue;
}
int f = getDistance(up.back(), u);
int pos = -1;
for(int u : up){
if(location[u] >= location[up.back()]-f){
pos = u;
break;
}
}
int t = f - (location[up.back()] - location[pos]);
if(dist0[u] == dist0[pos] + t){
stype[u] = 1;
location[u] = location[up.back()] - f;
}
else{
stype[u] = 2;
location[u] = location[0] + dist0[u];
up.pb(u);
}
}
vi down;
for(int u : left){
if(down.empty()){
stype[u] = 1;
location[u] = location[p] - distp[u];
down.pb(u);
continue;
}
int f = getDistance(down.back(), u);
int pos = -1;
for(int u : down){
if(location[u] <= location[down.back()] + f){
pos = u;
break;
}
}
int t = f - (location[pos] - location[down.back()]);
if(distp[u] == distp[pos] + t){
stype[u] = 2;
location[u] = location[down.back()] + f;
}
else{
stype[u] = 1;
location[u] = location[p] - distp[u];
down.pb(u);
}
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
380 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
380 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 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 |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
73 ms |
512 KB |
Output is correct |
2 |
Correct |
71 ms |
508 KB |
Output is correct |
3 |
Correct |
71 ms |
496 KB |
Output is correct |
4 |
Correct |
86 ms |
512 KB |
Output is correct |
5 |
Correct |
73 ms |
516 KB |
Output is correct |
6 |
Correct |
70 ms |
588 KB |
Output is correct |
7 |
Correct |
71 ms |
500 KB |
Output is correct |
8 |
Correct |
70 ms |
512 KB |
Output is correct |
9 |
Correct |
71 ms |
588 KB |
Output is correct |
10 |
Correct |
70 ms |
520 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
74 ms |
520 KB |
Output is correct |
2 |
Correct |
71 ms |
596 KB |
Output is correct |
3 |
Correct |
69 ms |
496 KB |
Output is correct |
4 |
Correct |
69 ms |
504 KB |
Output is correct |
5 |
Correct |
71 ms |
500 KB |
Output is correct |
6 |
Correct |
76 ms |
504 KB |
Output is correct |
7 |
Correct |
74 ms |
500 KB |
Output is correct |
8 |
Correct |
68 ms |
516 KB |
Output is correct |
9 |
Correct |
69 ms |
496 KB |
Output is correct |
10 |
Correct |
68 ms |
500 KB |
Output is correct |
11 |
Correct |
74 ms |
504 KB |
Output is correct |
12 |
Correct |
72 ms |
512 KB |
Output is correct |
13 |
Correct |
68 ms |
588 KB |
Output is correct |
14 |
Correct |
73 ms |
588 KB |
Output is correct |
15 |
Correct |
77 ms |
500 KB |
Output is correct |
16 |
Correct |
70 ms |
508 KB |
Output is correct |
17 |
Correct |
75 ms |
624 KB |
Output is correct |
18 |
Correct |
75 ms |
508 KB |
Output is correct |
19 |
Correct |
73 ms |
508 KB |
Output is correct |
20 |
Correct |
89 ms |
500 KB |
Output is correct |