Submission #1139467

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139467		mychecksedad	Rail (IOI14_rail)	C++20	30 / 100	33 ms	592 KiB

rail

#include "rail.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>


void findLocation(int n, int f, int location[], int stype[]){
	if(n == 1){
		location[0] = f;
		stype[0] = 1;
		return;
	}
	vector<pii> d(n);
	vector<bool> vis(n);
	vector<int> dist(n);
	for(int i = 1; i < n; ++i){
		d[i] = {getDistance(0, i), i};
		dist[i] = d[i].ff;
	}

	location[0] = f;
	stype[0] = 1;

	d[0] = {MOD, 0};
	sort(all(d));
	int R = d[0].ss, L = 0;
	
	vis[0] = 1;
	vis[R] = 1;

	location[R] = f + d[0].ff;
	stype[R] = 2;

	for(int i = 1; i + 1 < n; ++i){
		int y = getDistance(d[0].ss, d[i].ss);
		int x = d[i].ff;
		if(x == y + dist[d[0].ss] && y <= dist[d[0].ss]){ // inside
			location[d[i].ss] = location[d[0].ss] - y;
			stype[d[i].ss] = 1;
		}else if(x == y + dist[d[0].ss]){ // lefter
			int z = getDistance(d[i].ss, L);
			if(z == y + location[d[0].ss] - location[L] && y <= location[d[0].ss] - location[L]){ // inside
				stype[d[i].ss] = 2;
				location[d[i].ss] = location[L] + z;
			}else{ // lefter
				location[d[i].ss] = location[d[0].ss] - y;
				stype[d[i].ss] = 1;
				L = d[i].ss;
			}
		}else{ // righer
			int z = getDistance(d[i].ss, R);
			if(x == z + location[R] - f && z <= location[R] -  f){ // inside
				stype[d[i].ss] = 1;
				location[d[i].ss] = location[R] - z;
			}else{ // rigter
				location[d[i].ss] = f + x;
				stype[d[i].ss] = 2;
				R = d[i].ss;
			}
		}
	}
}

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