Submission #48593

#	Time	Username	Problem	Language	Result	Execution time	Memory
48593		gs12117	Rail (IOI14_rail)	C++11	100 / 100	186 ms	1100 KiB

rail

#include<vector>
#include<algorithm>
#include<map>
#include "rail.h"
int n;
int distz[5010];
int distf[5010];
int side[5010];
int vchk[5010];
struct stn {
	int loc, val;
	bool operator<(const stn&r)const {
		return val < r.val;
	}
};
void findLocation(int N, int first, int location[], int stype[])
{
	if (n == 1) {
		location[0] = first;
		stype[0] = 1;
		return;
	}
	n = N;
	distz[0] = 0;
	int f = -1;
	for (int i = 1; i < n; i++) {
		distz[i] = getDistance(0, i);
		if (f == -1 || distz[i] < distz[f])f = i;
	}
	int rdf = distz[f];
	distf[f] = 0;
	distf[0] = rdf;
	int g = 0;
	for (int i = 1; i < n; i++) {
		if (i == f)continue;
		distf[i] = getDistance(i, f);
		if (distz[i] == distf[i] + rdf)side[i] = 1;
		else side[i] = 0;
		if (distf[i] < distf[g])g = i;
	}
	side[0] = 1;
	int df = distf[g];
	location[f] = first + rdf;
	location[g] = location[f] - df;
	stype[f] = 2;
	stype[g] = 1;
	for (int i = 0; i < n; i++) {
		vchk[i] = 0;
	}
	vchk[f] = 1;
	vchk[g] = 1;
	std::vector<stn> l, r;
	for (int i = 0; i < n; i++) {
		if (i == f || i == g)continue;
		stn t;
		t.loc = i;
		t.val = distf[i];
		if (side[i] == 1)l.push_back(t);
		else r.push_back(t);
	}
	std::sort(l.begin(), l.end());
	std::sort(r.begin(), r.end());
	std::map<int,int> m;
	int pd = g;
	m[location[f]] = stype[f];
	m[location[g]] = stype[g];
	for (int i = 0; i < l.size(); i++) {
		int x = l[i].loc;
		int d = l[i].val;
		int pr = getDistance(pd, x);
		int pl = location[f] - location[pd];
		int p = d - pl;
		int q = (pr - p) / 2;
		int y = location[f] - (pl - q);
		int flag = 0;
		if (m[y] == 1)flag = 1;
		if (flag == 1) {
			stype[x] = 2;
			location[x] = location[pd] + pr;
			vchk[x] = 1;
			m[location[x]] = stype[x];
		}
		else {
			stype[x] = 1;
			location[x] = location[f] - pl - p;
			vchk[x] = 1;
			pd = x;
			m[location[x]] = stype[x];
		}
	}
	pd = f;
	for (int i = 0; i < r.size(); i++) {
		int x = r[i].loc;
		int d = r[i].val;
		int pr = getDistance(pd, x);
		int pl = location[pd] - location[g];
		int p = d - df - pl;
		int q = (pr - p) / 2;
		int y = location[g] + (pl - q);
		int flag = 0;
		if (m[y] == 2)flag = 1;
		if (flag == 1) {
			stype[x] = 1;
			location[x] = location[pd] - pr;
			vchk[x] = 1;
			m[location[x]] = stype[x];
		}
		else {
			stype[x] = 2;
			location[x] = location[g] + pl + p;
			vchk[x] = 1;
			pd = x;
			m[location[x]] = stype[x];
		}
	}
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:67:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < l.size(); i++) {
                  ~~^~~~~~~~~~
rail.cpp:92:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < r.size(); i++) {
                  ~~^~~~~~~~~~

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