Submission #424702

#	Time	Username	Problem	Language	Result	Execution time	Memory
424702		vanic	Rail (IOI14_rail)	C++14	30 / 100	107 ms	460 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 > 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;
	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;
		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;
				if(sol1[x]<sol1[l]){
					l=x;
				}
			}
		}
		pot.clear();
		if(!p){
			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();
		}
//		cout << l << ' ' << d << endl;
	}
}

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