# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
173712 |
2020-01-05T08:03:19 Z |
maximath_1 |
Rail (IOI14_rail) |
C++11 |
|
87 ms |
964 KB |
#include "rail.h"
#include<bits/stdc++.h>
using namespace std;
vector<pair<int, int> >v;
set<int>C, D;
void findLocation(int n, int first, int l[], int t[]){
l[0]=first; t[0]=1; //block 0, C station
for(int i=1; i<n; i++)
v.push_back({getDistance(0, i), i});
sort(v.begin(), v.end());
l[v[0].second]=first+v[0].first;
t[v[0].second]=2; //the first D station
C.insert(l[0]);
D.insert(l[v[0].second]);
int L=0, R=v[0].second;
for(int i=1; i<v.size(); i++){
int idx=v[i].second;
int lf=getDistance(idx, L);
int rg=getDistance(idx, R);
int lfcan=l[L]+lf, rgcan=l[R]-rg;
bool isC;
auto it1=--C.upper_bound(lfcan);
if(rg==lfcan-*it1+l[R]-*it1){
isC=false;
}else{
auto it2=D.upper_bound(rgcan);
if(it2!=D.end() && lf==*it2-rgcan+*it2-l[L]){
isC=true;
}else{
if(v[i].first==2*l[v[0].second]-l[0]-rgcan)
isC=true;
else isC=false;
}
}
if(isC){
l[idx]=rgcan;
t[idx]=1;
C.insert(l[idx]);
if(l[L]>l[idx]) L=idx;
}else{
l[idx]=lfcan;
t[idx]=2;
D.insert(l[idx]);
if(l[R]<l[idx]) R=idx;
}
}
}
Compilation message
rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:16:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1; i<v.size(); i++){
~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
85 ms |
760 KB |
Output is correct |
2 |
Correct |
86 ms |
888 KB |
Output is correct |
3 |
Correct |
86 ms |
764 KB |
Output is correct |
4 |
Correct |
85 ms |
760 KB |
Output is correct |
5 |
Correct |
85 ms |
760 KB |
Output is correct |
6 |
Correct |
86 ms |
760 KB |
Output is correct |
7 |
Correct |
87 ms |
888 KB |
Output is correct |
8 |
Correct |
85 ms |
760 KB |
Output is correct |
9 |
Correct |
85 ms |
760 KB |
Output is correct |
10 |
Correct |
87 ms |
760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
86 ms |
760 KB |
Output is correct |
2 |
Correct |
86 ms |
732 KB |
Output is correct |
3 |
Correct |
85 ms |
804 KB |
Output is correct |
4 |
Correct |
85 ms |
860 KB |
Output is correct |
5 |
Correct |
85 ms |
760 KB |
Output is correct |
6 |
Correct |
87 ms |
760 KB |
Output is correct |
7 |
Correct |
84 ms |
964 KB |
Output is correct |
8 |
Correct |
87 ms |
760 KB |
Output is correct |
9 |
Correct |
85 ms |
760 KB |
Output is correct |
10 |
Correct |
86 ms |
764 KB |
Output is correct |
11 |
Correct |
85 ms |
888 KB |
Output is correct |
12 |
Correct |
85 ms |
760 KB |
Output is correct |
13 |
Correct |
86 ms |
888 KB |
Output is correct |
14 |
Correct |
85 ms |
760 KB |
Output is correct |
15 |
Correct |
85 ms |
760 KB |
Output is correct |
16 |
Correct |
86 ms |
888 KB |
Output is correct |
17 |
Correct |
87 ms |
760 KB |
Output is correct |
18 |
Correct |
85 ms |
760 KB |
Output is correct |
19 |
Correct |
85 ms |
888 KB |
Output is correct |
20 |
Correct |
86 ms |
760 KB |
Output is correct |