Submission #159893

#	Time	Username	Problem	Language	Result	Execution time	Memory
159893		oolimry	Rail (IOI14_rail)	C++14	100 / 100	160 ms	1016 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
void findLocation(int N, int first, int location[], int stype[])
{
	typedef pair<int,int> ii;
	int n = N;
	vector<ii> order;
	int zeroDist[n];
	zeroDist[0] = 0;
	for(int i = 1;i < n;i++){
		zeroDist[i] = getDistance(i,0);
		order.push_back(ii(zeroDist[i],i));
	}
	sort(order.begin(),order.end());
	int a = order[0].second;
	int aDist[n];
	aDist[a] = 0;
	for(int i = 0;i < n;i++){
		if(i == a) continue;
		aDist[i] = getDistance(i,a);
	}
	
	int dd = order[0].first;
	stype[0] = 1;
	stype[a] = 2;
	location[0] = first;
	location[a] = first + dd;
	int second = first + dd;
	int l = 0;
	int r = a;
	map<int,int> mm;
	mm[first] = 1;
	mm[first+dd] = 2;
	for(int k = 1;k < (int) order.size();k++){
		int u = order[k].second;
		//cout << u << "\n";
		///left of a
		if(zeroDist[u] == aDist[u] + dd){
			///corner case, in between 0 and a
			if(aDist[u] < dd){
				stype[u] = 1;
				location[u] = location[a] - aDist[u];
				mm[location[u]] = stype[u];
			}
			///upwards
			else{
				int kk = getDistance(l,u);
				int x = kk - aDist[u] + aDist[l];
				x /= 2;
				int pos = location[l] + x;
				//cout << u << " " << pos << "\n";
				if(mm[pos] == 1){
					location[u] = location[l] + kk;
					stype[u] = 2;
					mm[location[u]] = stype[u];
				}
				else{
					location[u] = second - aDist[u];
					stype[u] = 1;
					mm[location[u]] = stype[u];
					l = u;
				} 
			}
		}
		else{
			int kk = getDistance(r,u);
			int x = kk - zeroDist[u] + zeroDist[r];
			x /= 2;
			int pos = location[r] - x;
			//cout << u << " " << pos << "\n";
			if(mm[pos] == 2){
				location[u] = location[r] - kk;
				stype[u] = 1;
				mm[location[u]] = stype[u];
			}
			else{
				location[u] = first + zeroDist[u];
				stype[u] = 2;
				mm[location[u]] = stype[u];
				r = u;
			} 
		}
	}

}

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