# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
122489 |
2019-06-28T12:23:05 Z |
someone_aa |
Rail (IOI14_rail) |
C++17 |
|
109 ms |
1016 KB |
#include "rail.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 5100;
ll d0[maxn], n;
ll dx[maxn];
map<int,bool> exist_right;
map<int,bool> exist_left;
void findLocation(int N, int first, int location[], int stype[])
{
n = N;
location[0] = first;
stype[0] = 1;
exist_left[location[0]] = true;
ll minval = LLONG_MAX;
ll x = -1;
for(int i=1;i<n;i++) {
d0[i] = getDistance(0, i);
if(d0[i] < minval) {
minval = d0[i];
x = i;
}
}
for(int i=1;i<n;i++) {
if(i == x) continue;
dx[i] = getDistance(i, x);
}
location[x] = first + d0[x];
stype[x] = 2;
exist_right[location[x]] = true;
//cout<<"Nearest is"<<x<<" at "<<location[x]<<"\n";
vector<pair<ll, ll> > lft, rght;
for(int i=1;i<n;i++) {
if(i == x) continue;
//cout<<i<<": "<<d0[i]<<", "<<dx[i]<<"\n";
if(d0[x] + dx[i] == d0[i]) {
lft.pb(mp(dx[i], i));
}
else {
rght.pb(mp(d0[i], i));
}
}
/*cout<<x<<"\n";
cout<<"on left: \n";
for(auto i:lft) {
cout<<i.first<<" "<<i.second<<"\n";
}
cout<<"and on right\n";
for(auto i:rght) {
cout<<i.first<<" "<<i.second<<"\n";
}*/
sort(lft.begin(), lft.end());
sort(rght.begin(), rght.end());
//cout<<"Levo: "<<lft.size()<<" i desno: "<<rght.size()<<"\n";
if(rght.size() > 0) {
int ind = rght[0].second;
int dst = d0[ind];
stype[ind] = 2;
location[ind] = location[0] + dst;
exist_right[location[ind]] = true;
int ind_limit = ind;
for(int i=1;i<rght.size();i++) {
ind = rght[i].second;
dst = d0[ind];
int temp = getDistance(ind_limit, ind);
ll z = abs(d0[ind] - d0[ind_limit] - temp);
z /= 2;
if(exist_right[location[ind_limit] - z]) {
// TYPE C
location[ind] = location[ind_limit] - temp;
stype[ind] = 1;
}
else {
// TYPE D
location[ind] = location[0] + d0[ind];
exist_right[location[ind]] = true;
stype[ind] = 2;
ind_limit = ind;
}
}
}
if(lft.size() > 0) {
int ind = lft[0].second;
int dst = lft[0].first;
stype[ind] = 1;
location[ind] = location[x] - dst;
exist_left[location[ind]] = true;
int ind_limit = ind;
for(int i=1;i<lft.size();i++) {
ind = lft[i].second;
dst = lft[i].first;
ll temp = getDistance(ind_limit, ind);
ll z = abs(dx[ind] - dx[ind_limit] - temp);
z /= 2;
// cout<<ind<<": "<<dst<<", "<<z<<"\n";
if(exist_left[location[ind_limit] + z]) {
// TYPE D
stype[ind] = 2;
location[ind] = location[ind_limit] + temp;
}
else {
// TYPE C
stype[ind] = 1;
location[ind] = location[x] - dx[ind];
ind_limit = ind;
exist_left[location[ind]] = true;
}
}
}
//return location[x];
}
Compilation message
rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:82:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1;i<rght.size();i++) {
~^~~~~~~~~~~~
rail.cpp:118:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1;i<lft.size();i++) {
~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
2 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
10 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
3 ms |
384 KB |
Output is correct |
8 |
Correct |
2 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
10 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
72 ms |
892 KB |
Output is correct |
2 |
Correct |
74 ms |
884 KB |
Output is correct |
3 |
Correct |
109 ms |
888 KB |
Output is correct |
4 |
Correct |
75 ms |
868 KB |
Output is correct |
5 |
Correct |
71 ms |
888 KB |
Output is correct |
6 |
Correct |
74 ms |
1016 KB |
Output is correct |
7 |
Correct |
73 ms |
888 KB |
Output is correct |
8 |
Correct |
72 ms |
760 KB |
Output is correct |
9 |
Correct |
70 ms |
744 KB |
Output is correct |
10 |
Correct |
73 ms |
760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
71 ms |
860 KB |
Output is correct |
2 |
Correct |
73 ms |
988 KB |
Output is correct |
3 |
Correct |
73 ms |
888 KB |
Output is correct |
4 |
Correct |
74 ms |
888 KB |
Output is correct |
5 |
Correct |
71 ms |
760 KB |
Output is correct |
6 |
Correct |
85 ms |
760 KB |
Output is correct |
7 |
Correct |
70 ms |
888 KB |
Output is correct |
8 |
Correct |
77 ms |
756 KB |
Output is correct |
9 |
Correct |
74 ms |
740 KB |
Output is correct |
10 |
Correct |
74 ms |
760 KB |
Output is correct |
11 |
Correct |
77 ms |
888 KB |
Output is correct |
12 |
Correct |
70 ms |
892 KB |
Output is correct |
13 |
Correct |
70 ms |
760 KB |
Output is correct |
14 |
Correct |
72 ms |
888 KB |
Output is correct |
15 |
Correct |
77 ms |
888 KB |
Output is correct |
16 |
Correct |
71 ms |
888 KB |
Output is correct |
17 |
Correct |
71 ms |
872 KB |
Output is correct |
18 |
Correct |
74 ms |
760 KB |
Output is correct |
19 |
Correct |
80 ms |
860 KB |
Output is correct |
20 |
Correct |
72 ms |
860 KB |
Output is correct |