Submission #779364

#	Time	Username	Problem	Language	Result	Execution time	Memory
779364		fatemetmhr	Rail (IOI14_rail)	C++17	30 / 100	45 ms	516 KiB

rail

//  ~ Be Name Khoda ~  //

#include "rail.h"
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  5e3   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   + 7;
const ll  inf   =  1e18;

int dis[maxn5];
vector <pair<int, int>> av;


void findLocation(int n, int first, int location[], int stype[])
{
	location[0] = first;
	stype[0] = 1;
	if(n == 1)
		return;
	for(int i = 1; i < n; i++){
		dis[i] = getDistance(0, i);
		av.pb({dis[i], i});
	}
	sort(all(av));
	int lastC = 0, lastD = -1;
	for(auto p : av){
		int v = p.se;
		if(lastD == -1){
			lastD = v;
			location[v] = location[0] + dis[v];
			stype[v] = 2;
			continue;
		}
		int disC = getDistance(lastC, v);
		int disD = getDistance(lastD, v);
		if(disC + location[lastC] - location[lastD] + 2 * (location[lastD] - location[lastC]) == disD){
			location[v] = disC + location[lastC];
			lastD = v;
			stype[v] = 2;
		}
		else{
			location[v] = location[lastD] - disD;
			if(location[v] > location[lastC])
				lastC = v;
			stype[v] = 1;
		}
	}
	return;
	//for(int i = 0; i < n; i++)
		//cout << "* " << location[i] << ' ' << stype[i] << endl;
	return;
}

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