# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
793112 | 2023-07-25T14:02:02 Z | Ronin13 | Rail (IOI14_rail) | C++17 | 55 ms | 4356 KB |
#include "rail.h" #include <bits/stdc++.h> #define ll long long #define ull unsigned ll #define f first #define s second #define pii pair<int,int> #define pll pair<ll,ll> #define pb push_back #define epb emplace_back using namespace std; const int nmax = 2000000; int val[nmax]; void findLocation(int N, int first, int location[], int stype[]) { int n = N; array<int, 2> a[n]; for(int i = 0; i < n; i++){ a[i][0] =getDistance(0, i); a[i][1] = i; } sort(a, a + n); int l = 0, r = a[1][1]; stype[r] = 2; stype[l] = 1; //cout << r; location[r] = first + a[1][0]; location[0] = first; val[first + a[1][0]] = 2; val[first] = 1; for(int i= 2; i < n; i++){ // int ind = a[i][1]; int d1 = getDistance(l, ind); int d2 = getDistance(r, ind); //cout << d1 << ' ' << d2 << "\n"; //cout << location[r] << "\n"; int p = location[l] + location[r] + d1 - d2; p /= 2; if(val[p] == 0){ if(p < first) stype[ind] = 1; else stype[ind] = 2; } else stype[ind] = 3 - val[p]; if(stype[ind] == 2){ location[ind] = location[l] + d1; val[location[ind]] = stype[ind]; if(location[ind] > location[r]) r = ind; } else{ location[ind] = location[r] - d2; val[location[ind]] = stype[ind]; if(location[ind] < location[l]) l = ind; } } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 0 ms | 384 KB | Output is correct |
3 | Correct | 1 ms | 384 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 0 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 | 1 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | 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 | 388 KB | Output is correct |
7 | Correct | 1 ms | 340 KB | Output is correct |
8 | Correct | 1 ms | 384 KB | Output is correct |
9 | Correct | 1 ms | 388 KB | Output is correct |
10 | Correct | 1 ms | 340 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 46 ms | 4100 KB | Output is correct |
2 | Correct | 47 ms | 4212 KB | Output is correct |
3 | Correct | 46 ms | 4356 KB | Output is correct |
4 | Correct | 46 ms | 4212 KB | Output is correct |
5 | Correct | 46 ms | 4224 KB | Output is correct |
6 | Correct | 46 ms | 4100 KB | Output is correct |
7 | Correct | 50 ms | 4152 KB | Output is correct |
8 | Correct | 55 ms | 4216 KB | Output is correct |
9 | Correct | 47 ms | 4228 KB | Output is correct |
10 | Correct | 47 ms | 4216 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 46 ms | 4088 KB | Output is correct |
2 | Correct | 46 ms | 4172 KB | Output is correct |
3 | Correct | 46 ms | 4344 KB | Output is correct |
4 | Correct | 47 ms | 4212 KB | Output is correct |
5 | Correct | 46 ms | 4220 KB | Output is correct |
6 | Correct | 50 ms | 4100 KB | Output is correct |
7 | Correct | 47 ms | 4092 KB | Output is correct |
8 | Correct | 46 ms | 4216 KB | Output is correct |
9 | Correct | 47 ms | 4104 KB | Output is correct |
10 | Correct | 47 ms | 4216 KB | Output is correct |
11 | Correct | 54 ms | 4084 KB | Output is correct |
12 | Correct | 55 ms | 4288 KB | Output is correct |
13 | Correct | 46 ms | 4104 KB | Output is correct |
14 | Correct | 46 ms | 4228 KB | Output is correct |
15 | Correct | 47 ms | 4232 KB | Output is correct |
16 | Correct | 49 ms | 4356 KB | Output is correct |
17 | Correct | 49 ms | 4216 KB | Output is correct |
18 | Correct | 48 ms | 4216 KB | Output is correct |
19 | Correct | 47 ms | 4228 KB | Output is correct |
20 | Correct | 46 ms | 4344 KB | Output is correct |