# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
424772 |
2021-06-12T09:54:31 Z |
vanic |
Rail (IOI14_rail) |
C++14 |
|
129 ms |
640 KB |
#include "rail.h"
#include <vector>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <cassert>
using namespace std;
const int maxn=5e3+5;
pair < int, int > dist[maxn];
vector < int > desne;
vector < int > lijeve;
vector < int > pot;
void findLocation(int n, int pos, int sol1[], int sol2[]){
for(int i=1; i<n; i++){
dist[i-1]={getDistance(0, i), i};
}
sol1[0]=pos;
sol2[0]=1;
sort(dist, dist+n-1);
int l=0;
lijeve.push_back(l);
int d=dist[0].second;
int x;
sol1[d]=pos+dist[0].first;
sol2[d]=2;
desne.push_back(d);
int q1, q2;
bool p;
for(int i=1; i<n-1; i++){
x=dist[i].second;
// cout << "na " << x << endl;
q1=getDistance(l, x);
q2=getDistance(d, x);
for(int j=0; j<(int)desne.size(); j++){
if(sol1[desne[j]]-sol1[l]<q1 && (!j || sol1[desne[j]]*2-q1-sol1[l]>sol1[desne[j-1]])){
pot.push_back(sol1[desne[j]]*2-q1-sol1[l]);
}
}
p=0;
for(int j=0; j<(int)pot.size(); j++){
if(sol1[d]-pot[j]==q2){
assert(!p);
assert(pot[j]>=0);
p=1;
sol1[x]=pot[j];
sol2[x]=1;
lijeve.push_back(x);
int poz=lijeve.size()-1;
while(poz>0 && sol1[lijeve[poz]]<sol1[lijeve[poz-1]]){
swap(lijeve[poz], lijeve[poz-1]);
poz--;
}
l=lijeve[0];
}
}
pot.clear();
if(p){
continue;
}
for(int j=0; j<(int)lijeve.size(); j++){
if(sol1[d]-sol1[lijeve[j]]<q2 && (j==(int)lijeve.size()-1 || sol1[lijeve[j]]*2+q2-sol1[d]<sol1[lijeve[j+1]])){
pot.push_back(sol1[lijeve[j]]*2+q2-sol1[d]);
}
}
for(int j=0; j<(int)pot.size(); j++){
if(pot[j]-sol1[l]==q1){
assert(!p);
p=1;
sol1[x]=pot[j];
sol2[x]=2;
desne.push_back(x);
int poz=desne.size()-1;
while(poz>0 && sol1[desne[poz]]<sol1[desne[poz-1]]){
swap(desne[poz], desne[poz-1]);
poz--;
}
d=desne.back();
}
}
pot.clear();
if(p){
continue;
}
if(q1-dist[i].first==sol1[0]-sol1[l]){
sol1[x]=sol1[l]+q1;
sol2[x]=2;
desne.push_back(x);
int poz=desne.size()-1;
while(poz>0 && sol1[desne[poz]]<sol1[desne[poz-1]]){
swap(desne[poz], desne[poz-1]);
poz--;
}
d=desne.back();
}
else{
sol1[x]=sol1[d]-q2;
sol2[x]=1;
lijeve.push_back(x);
int poz=lijeve.size()-1;
while(poz>0 && sol1[lijeve[poz]]<sol1[lijeve[poz-1]]){
swap(lijeve[poz], lijeve[poz-1]);
poz--;
}
l=lijeve[0];
}
// cout << l << ' ' << d << endl;
}
/* cout << "kraj--------" << endl;
for(int i=0; i<n; i++){
cout << sol2[i] << ' ' << sol1[i] << endl;
}*/
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
123 ms |
460 KB |
Output is correct |
2 |
Correct |
111 ms |
580 KB |
Output is correct |
3 |
Correct |
115 ms |
516 KB |
Output is correct |
4 |
Correct |
119 ms |
496 KB |
Output is correct |
5 |
Correct |
105 ms |
508 KB |
Output is correct |
6 |
Correct |
106 ms |
640 KB |
Output is correct |
7 |
Correct |
110 ms |
560 KB |
Output is correct |
8 |
Correct |
110 ms |
492 KB |
Output is correct |
9 |
Correct |
129 ms |
508 KB |
Output is correct |
10 |
Correct |
106 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
115 ms |
460 KB |
Output is correct |
2 |
Correct |
124 ms |
504 KB |
Output is correct |
3 |
Correct |
129 ms |
508 KB |
Output is correct |
4 |
Correct |
109 ms |
580 KB |
Output is correct |
5 |
Correct |
105 ms |
492 KB |
Output is correct |
6 |
Correct |
105 ms |
504 KB |
Output is correct |
7 |
Correct |
109 ms |
504 KB |
Output is correct |
8 |
Correct |
111 ms |
552 KB |
Output is correct |
9 |
Correct |
109 ms |
500 KB |
Output is correct |
10 |
Correct |
109 ms |
492 KB |
Output is correct |
11 |
Correct |
106 ms |
580 KB |
Output is correct |
12 |
Correct |
107 ms |
564 KB |
Output is correct |
13 |
Correct |
111 ms |
508 KB |
Output is correct |
14 |
Correct |
115 ms |
580 KB |
Output is correct |
15 |
Correct |
111 ms |
508 KB |
Output is correct |
16 |
Correct |
111 ms |
508 KB |
Output is correct |
17 |
Correct |
108 ms |
624 KB |
Output is correct |
18 |
Correct |
111 ms |
512 KB |
Output is correct |
19 |
Correct |
110 ms |
500 KB |
Output is correct |
20 |
Correct |
105 ms |
580 KB |
Output is correct |