Submission #341931

#	Time	Username	Problem	Language	Result	Execution time	Memory
341931		pit4h	Rail (IOI14_rail)	C++14	100 / 100	429 ms	26172 KiB

rail

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

const int MAXN = 5e3+1;
int mem[MAXN][MAXN];
int Distance(int x, int y) {
	if(mem[x][y]!=0) return mem[x][y];
	mem[x][y] = getDistance(x, y);
	return mem[x][y];
}
#define getDistance Distance

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;
			}
		}
	}
	if(res.nr==-1) cerr<<pos<<' '<<type<<'\n';
	assert(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;
}

Station check(int i, Station l, Station r, bool force=0) {
	Station res(-1, -1, -1);
	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++;	
			res = cand[j];
		}
	}
	assert(cnt_ok <= 1);
	if(force && res.nr==-1) res = cand[0];
	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;
		Station st = check(i, l, r);	
		if(st.nr==-1) {
			st = check(i, stations[0], r, 1);
		}
		stations.push_back(st);
		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: 26 / 26
• Subtask 4: 44 / 44