# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
287361 |
2020-08-31T16:28:00 Z |
egekabas |
Rail (IOI14_rail) |
C++14 |
|
84 ms |
632 KB |
#include "rail.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
int n;
void findLocation(int N, int first, int location[], int stype[]){
n = N;
location[0] = first;
stype[0] = 1;
pii lef = {first, 0};
vector<pii> vec;
for(int i = 1; i < n; ++i){
vec.pb({getDistance(0, i), i});
}
set<int> down = {first};
sort(all(vec));
location[vec[0].ss] = first + vec[0].ff;
stype[vec[0].ss] = 2;
pii rig = {location[vec[0].ss], vec[0].ss};
for(int i = 1; i < vec.size(); ++i){
int dis0 = vec[i].ff;
int idx = vec[i].ss;
int disl = getDistance(lef.ss, idx);
int disr = getDistance(rig.ss, idx);
auto it = down.upper_bound(lef.ff+disl);
if(it != down.begin() && disr == rig.ff-2*(*(--it))+lef.ff+disl){
stype[idx] = 2;
location[idx] = location[lef.ss]+disl;
rig = max(rig, {location[idx], idx});
}
else{
stype[idx] = 1;
location[idx] = location[rig.ss]-disr;
lef = min(lef, {location[idx], idx});
down.insert(location[idx]);
}
}
}
Compilation message
rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:31:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | for(int i = 1; i < vec.size(); ++i){
| ~~^~~~~~~~~~~~
rail.cpp:32:13: warning: unused variable 'dis0' [-Wunused-variable]
32 | int dis0 = vec[i].ff;
| ^~~~
# |
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 |
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 |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
416 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 |
Incorrect |
84 ms |
632 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
84 ms |
632 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |