# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
889348 |
2023-12-19T11:40:44 Z |
JakobZorz |
Rail (IOI14_rail) |
C++17 |
|
58 ms |
856 KB |
#include"rail.h"
#include<iostream>
#include<vector>
#include<algorithm>
typedef long long ll;
using namespace std;
void findLocation(int n,int first,int location[],int stype[]){
vector<pair<int,int>>dist0;
vector<int>dist_from_0(n);
for(int i=1;i<n;i++){
dist_from_0[i]=getDistance(0,i);
dist0.emplace_back(dist_from_0[i],i);
}
sort(dist0.begin(),dist0.end());
vector<int>left,right;
left.push_back(0);
right.push_back(0);
stype[0]=1;
location[0]=0;
//for(auto i:dist0)
//cout<<i.first<<" "<<i.second<<"\n";
for(auto[dist,i]:dist0){
if(right.size()==1){
right.push_back(i);
location[i]=dist;
stype[i]=2;
continue;
}
int dist1=getDistance(right[1],i);
if(dist1+dist_from_0[right[1]]==dist){ // i is on the left side
dist-=2*dist_from_0[right[1]];
bool done=false;
for(int j=0;j<(int)left.size()-1;j++){
int b=location[left[j]];
int a=location[left[j+1]];
int nloc=2*a+dist;
//cout<<"nloc "<<nloc+first<<" "<<a+first<<" "<<b+first<<"\n";
if(a<nloc&&nloc<b){
int dist2=getDistance(left[j+1],i);
//cout<<dist2<<" - "<<a<<" == "<<dist<<"\n";
if(dist2-a==dist){
done=true;
location[i]=nloc;
stype[i]=2;
}
}
}
if(!done){
left.push_back(i);
location[i]=-dist;
stype[i]=1;
}
}else{ // i is on the right side
bool done=false;
for(int j=1;j<(int)right.size()-1;j++){
int a=location[right[j]];
int b=location[right[j+1]];
int nloc=2*b-dist;
if(a<nloc&&nloc<b){
int dist2=getDistance(right[j+1],i);
if(dist2+b==dist){
done=true;
location[i]=nloc;
stype[i]=1;
}
}
}
if(!done){
right.push_back(i);
location[i]=dist;
stype[i]=2;
}
}
}
for(int i=0;i<n;i++){
location[i]+=first;
//cout<<stype[i]<<" "<<location[i]<<"\n";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
52 ms |
604 KB |
Output is correct |
2 |
Correct |
52 ms |
600 KB |
Output is correct |
3 |
Correct |
52 ms |
604 KB |
Output is correct |
4 |
Correct |
50 ms |
632 KB |
Output is correct |
5 |
Correct |
58 ms |
600 KB |
Output is correct |
6 |
Correct |
56 ms |
600 KB |
Output is correct |
7 |
Correct |
53 ms |
636 KB |
Output is correct |
8 |
Correct |
50 ms |
604 KB |
Output is correct |
9 |
Correct |
52 ms |
600 KB |
Output is correct |
10 |
Correct |
52 ms |
600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
57 ms |
856 KB |
Output is correct |
2 |
Correct |
54 ms |
604 KB |
Output is correct |
3 |
Correct |
50 ms |
604 KB |
Output is correct |
4 |
Correct |
52 ms |
648 KB |
Output is correct |
5 |
Correct |
53 ms |
600 KB |
Output is correct |
6 |
Correct |
56 ms |
600 KB |
Output is correct |
7 |
Correct |
52 ms |
604 KB |
Output is correct |
8 |
Correct |
51 ms |
604 KB |
Output is correct |
9 |
Correct |
51 ms |
632 KB |
Output is correct |
10 |
Correct |
51 ms |
604 KB |
Output is correct |
11 |
Incorrect |
52 ms |
604 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |