Submission #341897

#	Time	Username	Problem	Language	Result	Execution time	Memory
341897		pit4h	Rail (IOI14_rail)	C++14	30 / 100	85 ms	876 KiB

rail

#include "rail.h"
#include "bits/stdc++.h"
#define st first
#define nd second
#define mp make_pair
using namespace std;

struct Station {
	int nr, pos, type;	
	Station(int _nr, int _pos, int _type) {
		nr = _nr;
		pos = _pos;
		type = _type;
	}
	int distance(int Pos, int Type);
};
vector<Station> stations;
Station findPair(int pos, int type) {
	Station res(-1, -1, -1);
	for(Station st: stations) {
		if(type==0 && st.type==1 && pos < st.pos) {
			if(res.nr==-1 || abs(pos - st.pos) < abs(pos - res.pos)) {
				res = st;
			}
		}
		if(type==1 && st.type==0 && pos > st.pos) {
			if(res.nr==-1 || abs(pos - st.pos) < abs(pos - res.pos)) {
				res = st;
			}
		}
	}
	//assert(res.nr != -1);
	while(res.nr == -1){}
	return res;
}
int Station::distance(int Pos, int Type) {
	Station paired = findPair(pos, type);
	Station Paired = findPair(Pos, Type);
	int res = abs(pos - Pos);
	if((type==0 && pos > Pos) || (type==1 && pos < Pos)) res += 2*abs(pos - paired.pos);
	if((Type==0 && Pos > pos) || (Type==1 && Pos < pos)) res += 2*abs(Pos - Paired.pos);	
	return res;
}

void findLocation(int N, int first, int location[], int stype[]) {
	location[0] = first; stype[0] = 1;
	stations.push_back( Station(0, first, 0) );
	if(N==1) return;

	vector<pair<int, int>> vec(N-1);
	for(int i=1; i<N; ++i) {
		vec[i-1] = mp(getDistance(0, i), i);
	}
	sort(vec.begin(), vec.end());
	
	stations.push_back( Station(vec[0].nd, location[0] + vec[0].st, 1) );
	Station l = stations[0], r = stations[1];
	vec.erase(vec.begin());

	for(auto vi: vec) {
		int i = vi.nd;

		int dl = getDistance(l.nr, i), dr = getDistance(r.nr, i);	
		
		vector<Station> cand = {Station(i, l.pos+dl, 1), Station(i, r.pos-dr, 0)};

		int cnt_ok = 0;
		for(int j=0; j<2; ++j) {
			if(l.distance(cand[j].pos, cand[j].type) == dl && r.distance(cand[j].pos, cand[j].type) == dr) {
				cnt_ok++;	
				stations.push_back(cand[j]);
			}
		}
		assert(cnt_ok == 1);

		if(stations.back().pos < l.pos) l = stations.back();
		if(stations.back().pos > r.pos) r = stations.back();
	}

	for(Station st: stations) {
		location[st.nr] = st.pos;
		stype[st.nr] = st.type+1;
	}
	return;
}

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