# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
77914 |
2018-10-01T07:34:49 Z |
shoemakerjo |
Rail (IOI14_rail) |
C++14 |
|
120 ms |
5644 KB |
#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
#define maxm 2000010
#define pii pair<int, int>
#define C 1
#define D 2
//ooh, ooh, macros!
#define maxn 5010
int blk[maxm]; //check if something is there or not
int zdist[maxn];
int xdist[maxn];
void findLocation(int N, int first, int location[], int stype[])
{
//just directly set location and stype
location[0] = first;
stype[0] = C;
blk[first] = C;
vector<pii> stuff;
for (int i = 1; i < N; i++) {
zdist[i] = getDistance(0, i);
stuff.push_back(pii(zdist[i], i));
}
sort(stuff.begin(), stuff.end());
int X= stuff[0].second;
for (int j = 1; j < N; j++) {
if (j != X) xdist[j] = getDistance(X, j);
}
location[X] = location[0] + stuff[0].first;
stype[X] = D;
blk[location[X]] = D;
vector<int> onright;
vector<int> onleft;
for (int j = 1; j < N; j++) {
if (j == X) continue;
if (xdist[j] < zdist[X] && zdist[j] == zdist[X] + xdist[j]) {
//is in middle
location[j] = location[X] - xdist[j] ;
stype[j] = C;
blk[location[j]] = C;
// cout << j << " did this thing" << endl;
continue;
}
if (zdist[X] + xdist[j] == zdist[j]) {
// cout << j << " is on the right" << endl;
// onright.push_back(j);
onleft.push_back(j);
}
else {
// cout << j << " is on the left " << endl;
// onleft.push_back(j);
onright.push_back(j);
}
}
stuff.clear(); //i love using stuff
for (int vv : onright) {
stuff.push_back(pii(zdist[vv], vv));
}
sort(stuff.begin(), stuff.end());
if (stuff.size()) {
int fardind = stuff[0].second;
// cout << " fardind: " << fardind << endl;
location[fardind] = location[0] + stuff[0].first;
stype[fardind] = D;
blk[location[fardind]] = D;
for (int j = 1; j < stuff.size(); j++) {
// cout << " DOING " << vv << endl;
int vv = stuff[j].second;
// cout << " DOING " << vv << endl;
int nd = getDistance(vv, fardind);
int z = zdist[vv] - zdist[fardind] - nd;
z /= 2;
z = 0-z;
// cout << " z :: " << z << endl;
if (location[fardind] - z >= 0 && blk[location[fardind] - z] == D) {
// we are a C
stype[vv] = C;
int nloc = location[fardind] - nd;
location[vv] = nloc;
blk[nloc] = C;
}
else {
//we are the new furthest d
location[vv] = zdist[vv] + location[0];
stype[vv] = D;
blk[location[vv]] = D;
fardind = vv;
}
}
}
stuff.clear();
for (int vv : onleft) {
// cout << vv << " is on the left" << endl;
stuff.push_back(pii(xdist[vv], vv));
}
sort(stuff.begin(), stuff.end());
if (stuff.size()) {
int farcind = stuff[0].second;
// cout << "farcind: " << farcind << endl;
location[farcind] = location[X] - stuff[0].first;
stype[farcind] = C;
blk[location[farcind]] = C;
for (int j = 1; j < stuff.size(); j++) {
int vv = stuff[j].second;
// cout << "doing " << vv << endl;
int nd = getDistance(vv, farcind);
int z = xdist[vv] - xdist[farcind] - nd;
z /= 2;
z = 0-z;
if (location[farcind] + z >= 0 && blk[location[farcind] + z] == C) {
//we are a D
stype[vv] = D;
int nloc = location[farcind] + nd;
location[vv] = nloc;
blk[nloc] = D;
}
else {
//we are the new furthest C
location[vv] = location[X] - xdist[vv] ;
stype[vv] = C;
blk[location[vv]] = C;
farcind = vv;
}
}
}
//should be good to go
}
//make sure that we are correctly marking things!
Compilation message
rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:76:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 1; j < stuff.size(); j++) {
~~^~~~~~~~~~~~~~
rail.cpp:120:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 1; j < stuff.size(); j++) {
~~^~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
448 KB |
Output is correct |
3 |
Correct |
2 ms |
528 KB |
Output is correct |
4 |
Correct |
2 ms |
592 KB |
Output is correct |
5 |
Correct |
2 ms |
592 KB |
Output is correct |
6 |
Correct |
2 ms |
592 KB |
Output is correct |
7 |
Correct |
2 ms |
592 KB |
Output is correct |
8 |
Correct |
2 ms |
592 KB |
Output is correct |
9 |
Correct |
2 ms |
592 KB |
Output is correct |
10 |
Correct |
2 ms |
608 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
620 KB |
Output is correct |
2 |
Correct |
2 ms |
748 KB |
Output is correct |
3 |
Correct |
2 ms |
748 KB |
Output is correct |
4 |
Correct |
2 ms |
748 KB |
Output is correct |
5 |
Correct |
2 ms |
748 KB |
Output is correct |
6 |
Correct |
2 ms |
748 KB |
Output is correct |
7 |
Correct |
2 ms |
748 KB |
Output is correct |
8 |
Correct |
2 ms |
748 KB |
Output is correct |
9 |
Correct |
2 ms |
748 KB |
Output is correct |
10 |
Correct |
2 ms |
748 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
85 ms |
4476 KB |
Output is correct |
2 |
Correct |
87 ms |
4588 KB |
Output is correct |
3 |
Correct |
87 ms |
4732 KB |
Output is correct |
4 |
Correct |
90 ms |
4732 KB |
Output is correct |
5 |
Correct |
87 ms |
4732 KB |
Output is correct |
6 |
Correct |
91 ms |
4732 KB |
Output is correct |
7 |
Correct |
87 ms |
4732 KB |
Output is correct |
8 |
Correct |
86 ms |
4732 KB |
Output is correct |
9 |
Correct |
86 ms |
4732 KB |
Output is correct |
10 |
Correct |
92 ms |
4896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
85 ms |
4896 KB |
Output is correct |
2 |
Correct |
90 ms |
4896 KB |
Output is correct |
3 |
Correct |
85 ms |
4956 KB |
Output is correct |
4 |
Correct |
86 ms |
4956 KB |
Output is correct |
5 |
Correct |
92 ms |
4956 KB |
Output is correct |
6 |
Correct |
120 ms |
4956 KB |
Output is correct |
7 |
Correct |
87 ms |
4988 KB |
Output is correct |
8 |
Correct |
91 ms |
4988 KB |
Output is correct |
9 |
Correct |
87 ms |
5028 KB |
Output is correct |
10 |
Correct |
88 ms |
5204 KB |
Output is correct |
11 |
Correct |
98 ms |
5204 KB |
Output is correct |
12 |
Correct |
86 ms |
5204 KB |
Output is correct |
13 |
Correct |
96 ms |
5208 KB |
Output is correct |
14 |
Correct |
88 ms |
5376 KB |
Output is correct |
15 |
Correct |
87 ms |
5376 KB |
Output is correct |
16 |
Correct |
88 ms |
5464 KB |
Output is correct |
17 |
Correct |
87 ms |
5512 KB |
Output is correct |
18 |
Correct |
90 ms |
5512 KB |
Output is correct |
19 |
Correct |
118 ms |
5512 KB |
Output is correct |
20 |
Correct |
109 ms |
5644 KB |
Output is correct |