# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
15686 |
2015-07-15T08:35:37 Z |
gs14004 |
Rail (IOI14_rail) |
C++14 |
|
127 ms |
976 KB |
#include "rail.h"
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int,int> pi;
int dist0[5005], distmin[5005];
bool setCheck[5005];
vector<pi> v;
void make(int location[], int stype[], int x, int st){
vector<pi> tmp;
for(auto &i : v){
if(tmp.empty()){
stype[i.second] = x;
location[i.second] = location[st];
if(stype[i.second] == 1){
location[i.second] -= i.first;
}
else{
location[i.second] += i.first;
}
tmp.push_back(i);
continue;
}
int found = 0;
int longDist = getDistance(tmp.back().second, i.second);
for(auto &j : tmp){
int p = longDist;
if(x == 2){
p -= location[tmp.back().second] - location[j.second];
}
else{
p += location[tmp.back().second] - location[j.second];
}
if(j.first + p == i.first){
stype[i.second] = 3 - x;
location[i.second] = location[j.second];
if(stype[i.second] == 1){
location[i.second] -= p;
}
else{
location[i.second] += p;
}
found = 1;
break;
}
}
if(!found){
stype[i.second] = x;
location[i.second] = location[st];
if(stype[i.second] == 1){
location[i.second] -= i.first;
}
else{
location[i.second] += i.first;
}
tmp.push_back(i);
}
}
}
void findLocation(int N, int first, int location[], int stype[])
{
location[0] = first;
stype[0] = 1;
int minv = 1e9, minp = -1;
for(int i=1; i<N; i++){
dist0[i] = getDistance(0,i);
if(minv > dist0[i]){
minv = dist0[i];
minp = i;
}
}
location[minp] = first + minv;
stype[minp] = 2;
for(int i=1; i<N; i++){
if(i == minp) continue;
distmin[i] = getDistance(minp, i);
if(dist0[i] == dist0[minp] + distmin[i]){
setCheck[i] = 1;
}
}
for(int i=1; i<N; i++){
if(setCheck[i]){
v.push_back(pi(distmin[i], i));
}
}
sort(v.begin(), v.end());
make(location, stype, 1, minp);
v.clear();
for(int i=1; i<N; i++){
if(i != minp && !setCheck[i]){
v.push_back(pi(dist0[i] - dist0[minp], i));
}
}
sort(v.begin(), v.end());
make(location, stype, 2, minp);
v.clear();
}
# |
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 |
412 KB |
Output is correct |
4 |
Correct |
2 ms |
616 KB |
Output is correct |
5 |
Correct |
2 ms |
616 KB |
Output is correct |
6 |
Correct |
2 ms |
616 KB |
Output is correct |
7 |
Correct |
2 ms |
616 KB |
Output is correct |
8 |
Correct |
2 ms |
616 KB |
Output is correct |
9 |
Correct |
2 ms |
616 KB |
Output is correct |
10 |
Correct |
2 ms |
616 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
616 KB |
Output is correct |
2 |
Correct |
2 ms |
616 KB |
Output is correct |
3 |
Correct |
3 ms |
616 KB |
Output is correct |
4 |
Correct |
3 ms |
616 KB |
Output is correct |
5 |
Correct |
3 ms |
616 KB |
Output is correct |
6 |
Correct |
2 ms |
676 KB |
Output is correct |
7 |
Correct |
2 ms |
676 KB |
Output is correct |
8 |
Correct |
2 ms |
676 KB |
Output is correct |
9 |
Correct |
2 ms |
676 KB |
Output is correct |
10 |
Correct |
3 ms |
676 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
97 ms |
852 KB |
Output is correct |
2 |
Correct |
91 ms |
856 KB |
Output is correct |
3 |
Correct |
125 ms |
856 KB |
Output is correct |
4 |
Correct |
96 ms |
856 KB |
Output is correct |
5 |
Correct |
103 ms |
856 KB |
Output is correct |
6 |
Correct |
103 ms |
856 KB |
Output is correct |
7 |
Correct |
109 ms |
976 KB |
Output is correct |
8 |
Correct |
101 ms |
976 KB |
Output is correct |
9 |
Correct |
100 ms |
976 KB |
Output is correct |
10 |
Correct |
114 ms |
976 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
101 ms |
976 KB |
Output is correct |
2 |
Correct |
95 ms |
976 KB |
Output is correct |
3 |
Correct |
95 ms |
976 KB |
Output is correct |
4 |
Correct |
91 ms |
976 KB |
Output is correct |
5 |
Correct |
120 ms |
976 KB |
Output is correct |
6 |
Correct |
101 ms |
976 KB |
Output is correct |
7 |
Correct |
98 ms |
976 KB |
Output is correct |
8 |
Correct |
94 ms |
976 KB |
Output is correct |
9 |
Correct |
96 ms |
976 KB |
Output is correct |
10 |
Correct |
101 ms |
976 KB |
Output is correct |
11 |
Correct |
98 ms |
976 KB |
Output is correct |
12 |
Correct |
94 ms |
976 KB |
Output is correct |
13 |
Correct |
96 ms |
976 KB |
Output is correct |
14 |
Correct |
126 ms |
976 KB |
Output is correct |
15 |
Correct |
99 ms |
976 KB |
Output is correct |
16 |
Correct |
106 ms |
976 KB |
Output is correct |
17 |
Correct |
102 ms |
976 KB |
Output is correct |
18 |
Correct |
113 ms |
976 KB |
Output is correct |
19 |
Correct |
98 ms |
976 KB |
Output is correct |
20 |
Correct |
127 ms |
976 KB |
Output is correct |