Submission #424772

#	Time	Username	Problem	Language	Result	Execution time	Memory
424772		vanic	Rail (IOI14_rail)	C++14	100 / 100	129 ms	640 KiB

rail

#include "rail.h"
#include <vector>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <cassert>

using namespace std;

const int maxn=5e3+5;

pair < int, int > dist[maxn];
vector < int > desne;
vector < int > lijeve;
vector < int > pot;


void findLocation(int n, int pos, int sol1[], int sol2[]){
	for(int i=1; i<n; i++){
		dist[i-1]={getDistance(0, i), i};
	}
	sol1[0]=pos;
	sol2[0]=1;
	sort(dist, dist+n-1);
	int l=0;
	lijeve.push_back(l);
	int d=dist[0].second;
	int x;
	sol1[d]=pos+dist[0].first;
	sol2[d]=2;
	desne.push_back(d);
	int q1, q2;
	bool p;
	for(int i=1; i<n-1; i++){
		x=dist[i].second;
//		cout << "na " << x << endl;
		q1=getDistance(l, x);
		q2=getDistance(d, x);
		for(int j=0; j<(int)desne.size(); j++){
			if(sol1[desne[j]]-sol1[l]<q1 && (!j || sol1[desne[j]]*2-q1-sol1[l]>sol1[desne[j-1]])){
				pot.push_back(sol1[desne[j]]*2-q1-sol1[l]);
			}
		}
		p=0;
		for(int j=0; j<(int)pot.size(); j++){
			if(sol1[d]-pot[j]==q2){
				assert(!p);
				assert(pot[j]>=0);
				p=1;
				sol1[x]=pot[j];
				sol2[x]=1;
				lijeve.push_back(x);
				int poz=lijeve.size()-1;
				while(poz>0 && sol1[lijeve[poz]]<sol1[lijeve[poz-1]]){
					swap(lijeve[poz], lijeve[poz-1]);
					poz--;
				}
				l=lijeve[0];
			}
		}
		pot.clear();
		if(p){
			continue;
		}

		for(int j=0; j<(int)lijeve.size(); j++){
			if(sol1[d]-sol1[lijeve[j]]<q2 && (j==(int)lijeve.size()-1 || sol1[lijeve[j]]*2+q2-sol1[d]<sol1[lijeve[j+1]])){
				pot.push_back(sol1[lijeve[j]]*2+q2-sol1[d]);
			}
		}
		for(int j=0; j<(int)pot.size(); j++){
			if(pot[j]-sol1[l]==q1){
				assert(!p);
				p=1;
				sol1[x]=pot[j];
				sol2[x]=2;
				desne.push_back(x);
				int poz=desne.size()-1;
				while(poz>0 && sol1[desne[poz]]<sol1[desne[poz-1]]){
					swap(desne[poz], desne[poz-1]);
					poz--;
				}
				d=desne.back();
			}
		}
		pot.clear();
		if(p){
			continue;
		}


		if(q1-dist[i].first==sol1[0]-sol1[l]){
			sol1[x]=sol1[l]+q1;
			sol2[x]=2;
			desne.push_back(x);
			int poz=desne.size()-1;
			while(poz>0 && sol1[desne[poz]]<sol1[desne[poz-1]]){
				swap(desne[poz], desne[poz-1]);
				poz--;
			}
			d=desne.back();
		}
		else{
			sol1[x]=sol1[d]-q2;
			sol2[x]=1;
			lijeve.push_back(x);
			int poz=lijeve.size()-1;
			while(poz>0 && sol1[lijeve[poz]]<sol1[lijeve[poz-1]]){
				swap(lijeve[poz], lijeve[poz-1]);
				poz--;
			}
			l=lijeve[0];
		}
//		cout << l << ' ' << d << endl;
	}
/*	cout << "kraj--------" << endl;
	for(int i=0; i<n; i++){
		cout << sol2[i] << ' ' << sol1[i] << endl;
	}*/
}

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