Submission #282605

#	Time	Username	Problem	Language	Result	Execution time	Memory
282605		amoo_safar	Rail (IOI14_rail)	C++17	100 / 100	99 ms	768 KiB

rail

#include "rail.h"

#include <bits/stdc++.h>

#define pb push_back

using namespace std;

const int N = 5010;

int d0[N];
int d1[N];

void findLocation(int n, int fst, int loc[], int sty[]){
	for(int i = 1; i < n; i++)
		d0[i] = getDistance(0, i);
	int mn = 1;
	for(int i = 2; i < n; i++)
		if(d0[i] < d0[mn])
			mn = i;

	//cerr << "mn : " << mn << '\n';

	d1[0] = d0[mn];
	for(int i = 1; i < n; i++)
		d1[i] = getDistance(mn, i);

	int L = d0[mn];

	loc[0] = fst; sty[0] = 1;
	loc[mn] = fst + L; sty[mn] = 2;
	vector<int> A, B, C;

	for(int i = 1; i < n; i++){
		if(i == mn) continue;
		if(d0[i] == d1[i] + L){
			if(d1[i] < L) B.pb(i);
			else A.pb(i);
		} else {
			C.pb(i);
		}
	}
	for(auto x : B){
		sty[x] = 1;
		loc[x] = loc[0] + L - d1[x];
	}
	/*
	cerr << "A : ";
	for(auto x : A) cerr << x << ' ';
	cerr << '\n';

	cerr << "B : ";
	for(auto x : B) cerr << x << ' ';
	cerr << '\n';

	cerr << "C : ";
	for(auto x : C) cerr << x << ' ';
	cerr << '\n';		
	*/

	sort(A.begin(), A.end(), [&](int i, int j){
		return d1[i] < d1[j];
	});
	vector<int> V;
	int sz, ds, la;
	if(!A.empty()){
		la = A[0];
		loc[la] = loc[mn] - d1[la];
		V.pb(la);
		sty[la] = 1;
		sz = A.size();
		for(int i = 1; i < sz; i++){
			ds = getDistance(la, A[i]);
			int pos = loc[la] + ds;
			bool flg = false;
			for(auto x : V){
				if(loc[x] <= pos){
					if(d1[A[i]] == abs(loc[x] - pos) + d1[x]) flg = true;
					break;
				}
			}
			if(flg){
				loc[A[i]] = pos;
				sty[A[i]] = 2;
			} else {
				loc[A[i]] = loc[mn] - d1[A[i]];
				sty[A[i]] = 1;
				la = A[i];
				V.pb(la);
			}
		}
	}

	sort(C.begin(), C.end(), [&](int i, int j){
		return d0[i] < d0[j];
	});
	if(!C.empty()){
		V.clear();
		la = C[0];
		loc[la] = loc[0] + d0[la];
		V.pb(la);
		sty[la] = 2;
		sz = C.size();
		for(int i = 1; i < sz; i++){
			ds = getDistance(la, C[i]);
			int pos = loc[la] - ds;
			bool flg = false;
			for(auto x : V){
				if(loc[x] >= pos){
					if(d0[C[i]] == abs(loc[x] - pos) + d0[x]) flg = true;
					break;
				}
			}
			if(flg){
				loc[C[i]] = pos;
				sty[C[i]] = 1;
			} else {
				loc[C[i]] = loc[0] + d0[C[i]];
				sty[C[i]] = 2;
				la = C[i];
				V.pb(la);
			}
		}
	}
	/*
	cerr << "sty : ";
	for(int i = 0; i < n; i++) cerr << sty[i] << ' ';
	cerr << '\n';
	*/
}
/*
1
4
1 1
2 4
2 7
2 9

2
6
1 3
2 6
2 7
1 1
1 0
2 8


*/

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