Submission #747117

#	Time	Username	Problem	Language	Result	Execution time	Memory
747117		MODDI	Rail (IOI14_rail)	C++14	100 / 100	89 ms	624 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define mp make_pair
#define pb push_back
void findLocation(int N, int first, int location[], int stype[])
{
	vector<int> dist0(N);
	location[0] = first;stype[0] = 1;
	for(int i = 1; i <= N; i++){
		int here = getDistance(0, i);
		stype[i] = 0;
		dist0[i] = here;
	}
	vi pos(N-1), distp(N);
	iota(pos.begin(), pos.end(), 1);
	sort(pos.begin(), pos.end(), [&](int a, int b){ 
		return dist0[a] < dist0[b];
	});
	int p = pos[0];
	stype[p] = 2;
	location[p] = first + dist0[p];
	vi left, right;
	for(int u : pos){
		if(u != p){
			distp[u] = getDistance(p, u);
			if(dist0[u] == dist0[p] + distp[u]){
				if(distp[u] < dist0[p]){
					stype[u] = 1;
					location[u] = location[p] - distp[u];
				}
				else
					left.pb(u);
			}
			else	right.pb(u);
		}
	}
	vi up;
	for(int u : right){
		if(up.empty()){
			up.pb(u);
			stype[u] = 2;
			location[u] = location[0] + dist0[u];
			continue;
		}
		int f = getDistance(up.back(), u);
		int pos = -1;
		for(int u : up){
			if(location[u] >= location[up.back()]-f){
				pos = u;
				break;
			}
		}
		int t = f - (location[up.back()] - location[pos]);
		if(dist0[u] == dist0[pos] + t){
			stype[u] = 1;
			location[u] = location[up.back()] - f;
		}
		else{
			stype[u] = 2;
			location[u] = location[0] + dist0[u];
			up.pb(u);
		}
	}
	vi down;
	for(int u : left){
		if(down.empty()){
			stype[u] = 1;
			location[u] = location[p] - distp[u];
			down.pb(u);
			continue;
		}
		int f = getDistance(down.back(), u);
		int pos = -1;
		for(int u : down){
			if(location[u] <= location[down.back()] + f){
				pos = u;
				break;
			}
		}
		int t = f - (location[pos] - location[down.back()]);
		if(distp[u] == distp[pos] + t){
			stype[u] = 2;
			location[u] = location[down.back()] + f;
		}
		else{
			stype[u] = 1;
			location[u] = location[p] - distp[u];
			down.pb(u);
		}
	}
}

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