Submission #349610

#	Time	Username	Problem	Language	Result	Execution time	Memory
349610		amunduzbaev	Rail (IOI14_rail)	C++14	100 / 100	91 ms	4460 KiB

rail

#include "rail.h"
 
#ifndef EVAL
#include "grader.cpp"
#endif

#include <bits/stdc++.h>
using namespace std;
 
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define fastios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define Pi acos(-1);
#define mod 1e9+7
#define inf 1e18
 
typedef long long ll;
//#define int ll
typedef long double ld;
typedef pair<int, int> pii; 
typedef pair<ll, ll> pll; 
typedef vector<ll> vll;
typedef vector<int> vii;
typedef vector<pll> vpll;
typedef vector<pii> vpii;
template<class T> bool umin(T& a, const T& b) {return a > b? a = b, true:false;}
template<class T> bool umax(T& a, const T& b) {return a < b? a = b, true:false;}
 
const int N = 2e5+5, MM = 1e6+5;;
 
int d0[N], d1[N], used[MM];
 
void findLocation(int n, int cc, int loc[], int t[]){
	int mn = 1;
	for(int i=1;i<n;i++){
		d0[i] = getDistance(0, i);
		if(d0[mn] > d0[i]) mn = i;
	}
	loc[0] = cc, t[0] = 1, used[loc[0]] = 1;
	if(n == 1) return;
	loc[mn] = cc + d0[mn], t[mn] = 2, used[loc[mn]] = 2;
	
	d1[0] = d0[mn];
	for(int i=1;i<n;i++){
		if(i == mn) continue;
		d1[i] = getDistance(mn, i);
	}
	
	//for(int i=0;i<n;i++) cout<<d0[i]<<" ";
	//cout<<"\n";
	//for(int i=0;i<n;i++) cout<<d1[i]<<" ";
	//cout<<"\n";
	
	vpii l, r;
	for(int i=1;i<n;i++){
		if(i != mn){
			if(d0[i] == d0[mn] + d1[i]){
				if(d0[mn] > d1[i]){
					t[i] = 1;
					loc[i] = loc[mn] - d1[i];
					used[loc[i]] = 1;
				}else l.pb({d1[i], i});
			}else r.pb({d0[i], i});
		}
	}
	
	sort(all(l));
	sort(all(r));
	int R = mn;
	for(auto x : r){
		//cout<<x.ss<<" ";
		int i = x.ss;
		int tt = getDistance(R, i);
		int gap = (d0[R] + tt - d0[i])/2;
		
		//cout<<R<<" "<<tt<<" "<<d0[i]<<" "<<d0[R]<<"\n";
		//cout<<i<<" "<<tt<<" "<<gap<<"\n";
		if(used[loc[R] - gap] == 2){
			loc[i] = loc[R] - tt;
			t[i] = 1;
			used[loc[i]] = 1;
		}else{
			loc[i] = cc + d0[i];
			t[i] = 2;
			used[loc[i]] = 2;
			R = i;
		}
		//cout<<loc[i]<<" "<<t[i]<<"\n";
	} 
	//cout<<"\n";
	int L = 0;
	for(auto x : l){
		//cout<<x.ss<<" ";
		int i = x.ss;
		int tt = getDistance(L, i);
		int gap = (d1[L] + tt - d1[i])/2;
		if(used[loc[L] + gap] == 1){
			loc[i] = loc[L] + tt;
			t[i] = 2;
			used[loc[i]] = 2;
		}else{
			loc[i] = loc[mn] - d1[i];
			t[i] = 1;
			used[loc[i]] = 1;
			L = i;
		}
	}
	
	//for(int i=0;i<n;i++) cout<<t[i]<<" "<<loc[i]<<"\n";
}
/*

1
8
1 4
1 1
1 6
2 2
2 3
2 5
2 7
2 8

*/

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