Submission #77905

#	Time	Username	Problem	Language	Result	Execution time	Memory
77905		shoemakerjo	Rail (IOI14_rail)	C++14	30 / 100	91 ms	5228 KiB

rail

#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]) {
			//is in middle 
			location[j] = zdist[X] + location[0] - xdist[j] ;
			stype[j] = C;
			blk[location[j]] = C;
			continue;
		}
		if (zdist[X] + zdist[j] == xdist[j]) {
			onright.push_back(j);
		}
		else onleft.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;
		location[fardind] = location[0] + stuff[0].first;
		stype[fardind] = D;
		blk[location[fardind]] = D; 
		for (int j = 1; j < stuff.size(); j++) {

			int vv = stuff[j].second;
			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;
		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 (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:68:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 1; j < stuff.size(); j++) {
                   ~~^~~~~~~~~~~~~~
rail.cpp:108:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 1; j < stuff.size(); j++) {
                   ~~^~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 22 / 22
• Subtask 3: 0 / 26
• Subtask 4: 0 / 44