# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
171168 |
2019-12-27T16:13:38 Z |
AlexLuchianov |
Rail (IOI14_rail) |
C++14 |
|
156 ms |
2812 KB |
#include "rail.h"
#include <map>
#include <vector>
#include <algorithm>
#include <iostream>
#include <fstream>
std::ofstream out ("data.out");
using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))
int const nmax = 5000;
int const inf = 1000000000;
std::map<std::pair<int,int>, int> cost;
int getcost(int x, int y){
if(cost.find({x, y}) == cost.end())
cost[{y, x}] = cost[{x, y}] = getDistance(x, y);
return cost[{x, y}];
}
struct Train{
int id;
int dist;
bool operator < (Train const &a) const{
return dist < a.dist;
}
};
std::map<int,char> type;
int mark[1 + nmax];
void findLocation(int N, int first, int location[], int stype[])
{
int pos = 1;
for(int i = 1;i < N; i++)
if(getcost(0, i) < getcost(0, pos))
pos = i;
location[0] = first;
stype[0] = 1;
type[location[0]] = 'C';
location[pos] = first + getcost(0, pos);
stype[pos] = 2;
type[location[pos]] = 'D';
std::vector<Train> v;
for(int i = 1; i < N; i++)
if(i != pos)
v.push_back({i, getcost(0, i)});
std::sort(v.begin(), v.end());
int last1 = 0, last2 = pos;
for(int i = 0; i < v.size(); i++){
int id = v[i].id;
if(getcost(0, pos) + getcost(pos, id) != getcost(0, id)){
int x = location[last2] - getcost(last2, id);
int y = (getcost(0, id) + x + location[0]) / 2;
if(getcost(0, id) == (2 * y - location[0] - x) && type[y] == 'D'){
location[id] = x;
stype[id] = 1;
type[location[id]] = 'C';
} else {
location[id] = location[0] + getcost(0, id);
stype[id] = 2;
type[location[id]] = 'D';
}
mark[id] = 1;
} else {
int x = location[last1] + getcost(last1, id);
int y = (x + location[pos] - getcost(pos, id)) / 2;
if(getcost(pos, id) == (x + location[pos] - 2 * y) && type[y] == 'C'){
location[id] = x;
stype[id] = 2;
type[location[id]] = 'D';
} else {
location[id] = location[pos] - getcost(pos, id);
stype[id] = 1;
type[location[id]] = 'C';
}
mark[id] = 2;
}
if(stype[id] == 2 && location[last2] < location[id])
last2 = id;
if(stype[id] == 1 && location[id] < location[last1])
last1 = id;
//std::cout << id << " " << location[id] << " " << stype[id] << '\n';
}
//std::cout << '\n';
//*
//std::cout << 0 << " " << location[0] << '\n';
//std::cout << pos << " " << location[pos] << '\n';
/*
for(int i = 0; i < N; i++)
out << stype[i] << " " << location[i] << " " << mark[i] << " " << getcost(0, i) << " " << getcost(pos, i) << '\n';
//*/
}
/*
1
5
1 1
1 2
2 6
2 7
2 8
*/
Compilation message
rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:58:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; 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 |
3 ms |
376 KB |
Output is correct |
4 |
Correct |
3 ms |
376 KB |
Output is correct |
5 |
Correct |
3 ms |
504 KB |
Output is correct |
6 |
Correct |
2 ms |
504 KB |
Output is correct |
7 |
Correct |
3 ms |
376 KB |
Output is correct |
8 |
Correct |
3 ms |
504 KB |
Output is correct |
9 |
Correct |
5 ms |
504 KB |
Output is correct |
10 |
Correct |
3 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
504 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
504 KB |
Output is correct |
5 |
Correct |
3 ms |
380 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
3 ms |
504 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 |
110 ms |
2692 KB |
Output is correct |
2 |
Correct |
108 ms |
2680 KB |
Output is correct |
3 |
Correct |
109 ms |
2680 KB |
Output is correct |
4 |
Correct |
115 ms |
2732 KB |
Output is correct |
5 |
Correct |
119 ms |
2652 KB |
Output is correct |
6 |
Correct |
116 ms |
2652 KB |
Output is correct |
7 |
Correct |
112 ms |
2808 KB |
Output is correct |
8 |
Correct |
117 ms |
2740 KB |
Output is correct |
9 |
Correct |
110 ms |
2764 KB |
Output is correct |
10 |
Correct |
111 ms |
2684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
108 ms |
2652 KB |
Output is correct |
2 |
Correct |
111 ms |
2684 KB |
Output is correct |
3 |
Correct |
109 ms |
2644 KB |
Output is correct |
4 |
Correct |
110 ms |
2680 KB |
Output is correct |
5 |
Correct |
112 ms |
2680 KB |
Output is correct |
6 |
Correct |
103 ms |
2724 KB |
Output is correct |
7 |
Correct |
110 ms |
2692 KB |
Output is correct |
8 |
Correct |
117 ms |
2680 KB |
Output is correct |
9 |
Correct |
112 ms |
2808 KB |
Output is correct |
10 |
Correct |
113 ms |
2680 KB |
Output is correct |
11 |
Correct |
112 ms |
2808 KB |
Output is correct |
12 |
Correct |
107 ms |
2680 KB |
Output is correct |
13 |
Correct |
112 ms |
2692 KB |
Output is correct |
14 |
Correct |
109 ms |
2680 KB |
Output is correct |
15 |
Correct |
110 ms |
2812 KB |
Output is correct |
16 |
Correct |
112 ms |
2808 KB |
Output is correct |
17 |
Correct |
156 ms |
2808 KB |
Output is correct |
18 |
Correct |
122 ms |
2680 KB |
Output is correct |
19 |
Correct |
108 ms |
2680 KB |
Output is correct |
20 |
Correct |
112 ms |
2664 KB |
Output is correct |