# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
791747 |
2023-07-24T09:31:35 Z |
NothingXD |
Rail (IOI14_rail) |
C++17 |
|
82 ms |
568 KB |
#include "rail.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef complex<double> point;
void debug_out(){cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
cerr << H << ' ';
debug_out(T...);
}
#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
const int maxn = 5e3 + 10;
int n, h[maxn][2], idx[maxn];
bool cmp(int x, int y){
return h[x][0] < h[y][0];
}
void findLocation(int N, int first, int loc[], int type[]){
n = N;
for (int i = 1; i < n; i++){
h[i][0] = getDistance(0, i);
idx[i] = i;
}
sort(idx, idx + n, cmp);
h[0][1] = h[idx[1]][0];
for (int i = 1; i < n; i++){
if (i == idx[1]) continue;
h[i][1] = getDistance(idx[1], i);
}
loc[0] = first;
loc[idx[1]] = first + h[idx[1]][0];
type[0] = 1;
type[idx[1]] = 2;
int l = 0, r = idx[1];
for (int i = 2; i < n; i++){
if (h[idx[1]][0] + h[idx[i]][1] == h[idx[i]][0]){
if (h[idx[i]][1] <= h[idx[1]][0]){
type[idx[i]] = 1;
loc[idx[i]] = loc[idx[1]] - h[idx[i]][1];
continue;
}
int dis = getDistance(l, idx[i]);
int tmp = (dis + h[idx[i]][1] - h[l][1]) / 2;
tmp = dis - tmp;
tmp += loc[l];
bool flg = true;
for (int j = 0; j < i; j++){
if (loc[idx[j]] == tmp && type[idx[j]] == 1) flg = false;
}
if (flg){
loc[idx[i]] = loc[idx[1]] - h[idx[i]][1];
type[idx[i]] = 1;
l = idx[i];
}
else{
loc[idx[i]] = loc[l] + dis;
type[idx[i]] = 2;
}
continue;
}
int dis = getDistance(r, idx[i]);
int tmp = (dis + h[idx[i]][0] - h[r][0]) / 2;
tmp = dis - tmp;
tmp = loc[r] - tmp;
bool flg = true;
for (int j = 0; j < i; j++){
if (loc[idx[j]] == tmp && type[idx[j]] == 2) flg = false;
}
if (flg){
loc[idx[i]] = loc[idx[0]] + h[idx[i]][0];
type[idx[i]] = 2;
r = idx[i];
}
else{
loc[idx[i]] = loc[r] - dis;
type[idx[i]] = 1;
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
56 ms |
468 KB |
Output is correct |
2 |
Correct |
56 ms |
516 KB |
Output is correct |
3 |
Correct |
57 ms |
524 KB |
Output is correct |
4 |
Correct |
58 ms |
468 KB |
Output is correct |
5 |
Correct |
57 ms |
472 KB |
Output is correct |
6 |
Correct |
57 ms |
468 KB |
Output is correct |
7 |
Correct |
75 ms |
520 KB |
Output is correct |
8 |
Correct |
66 ms |
524 KB |
Output is correct |
9 |
Correct |
56 ms |
476 KB |
Output is correct |
10 |
Correct |
57 ms |
520 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
57 ms |
476 KB |
Output is correct |
2 |
Correct |
59 ms |
480 KB |
Output is correct |
3 |
Correct |
56 ms |
476 KB |
Output is correct |
4 |
Correct |
61 ms |
480 KB |
Output is correct |
5 |
Correct |
56 ms |
472 KB |
Output is correct |
6 |
Correct |
57 ms |
476 KB |
Output is correct |
7 |
Correct |
58 ms |
472 KB |
Output is correct |
8 |
Correct |
63 ms |
472 KB |
Output is correct |
9 |
Correct |
66 ms |
468 KB |
Output is correct |
10 |
Correct |
57 ms |
468 KB |
Output is correct |
11 |
Correct |
56 ms |
468 KB |
Output is correct |
12 |
Correct |
56 ms |
508 KB |
Output is correct |
13 |
Correct |
58 ms |
520 KB |
Output is correct |
14 |
Correct |
57 ms |
528 KB |
Output is correct |
15 |
Correct |
56 ms |
504 KB |
Output is correct |
16 |
Correct |
56 ms |
516 KB |
Output is correct |
17 |
Correct |
56 ms |
556 KB |
Output is correct |
18 |
Correct |
61 ms |
568 KB |
Output is correct |
19 |
Correct |
82 ms |
504 KB |
Output is correct |
20 |
Correct |
60 ms |
564 KB |
Output is correct |