Submission #121219

#	Time	Username	Problem	Language	Result	Execution time	Memory
121219		Rudy420	Rail (IOI14_rail)	C++17	100 / 100	80 ms	760 KiB

rail

#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define ll long long
#define pi pair<int,int>
#define pl pair<ll,ll>
#define pd pair<double,double>
#define ld long double
#define pld pair<ld,ld>
#define lg length()
#define sz size()
#define vi vector<int>
#define vl vector<ll>
#define vp vector<pi>
#define vpl vector<pl>
#define pb push_back
#define INF 1000000005
#define LINF 1000000000000000005
#ifdef LOCAL_DEFINE
    mt19937 rng(69);
#else
    seed_seq seq{
        (uint64_t) chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count(),
        //(uint64_t) __builtin_ia32_rdtsc(),
        //(uint64_t) (uintptr_t) make_unique<char>().get()
    };
    mt19937 rng(seq);
#endif

#include "rail.h"


void findLocation(int n, int x, int p[], int t[])
{
    if(n==1){
        p[0]=x; t[0]=1;
        return;
    }
    int a[n+5],b[n+5];
    for(int i=1;i<n;i++) a[i]=getDistance(0,i);
    int mn=INF,y=-1;
    for(int i=1;i<n;i++){
        if(a[i]<mn) mn=a[i],y=i;
    }
    for(int i=0;i<n;i++){
        if(i==y) continue;
        b[i]=getDistance(y,i);
    }
    mn=INF;
	int z=-1;
    for(int i=0;i<n;i++){
    	if(i==y) continue;
        if(b[i]<mn) mn=b[i],z=i;
    }
    int diff=b[z]-a[y];
    p[z]=x-diff;
    p[y]=p[z]+b[z];
    t[z]=1;
    t[y]=2;
    for(int i=0;i<n;i++){
        a[i]+=diff;
    }
    vector <pi> l,r;
	vector <int> u,v;
    for(int i=0;i<n;i++){
        if(i==y || i==z) continue;
        if(i==0) a[i]=2*(p[y]-p[z])-diff;
        if(a[i]>b[i]) l.pb({b[i],i});
        else r.pb({a[i],i});
    }
    
	sort(l.begin(),l.end());
	u.pb(p[z]);
	int f=z;
	for(pi i : l){
		int d=getDistance(i.y,f);
		p[i.y]=p[f]+d;
		if(p[i.y]>=p[z]){
			p[i.y]=p[y]-b[i.y];
			t[i.y]=1;
			u.pb(p[i.y]);
			f=i.y;
		}
		int c=*(lower_bound(u.begin(),u.end(),p[i.y],greater<int>()));
		if(b[i.y]==p[i.y]+p[y]-2*c && p[i.y]!=c){
			t[i.y]=2;
		}
		else{
			p[i.y]=p[y]-b[i.y];
			t[i.y]=1;
			u.pb(p[i.y]);
			f=i.y;
		}
	}
	
	sort(r.begin(),r.end());
	v.pb(p[y]);
	f=y;
	for(pi i : r){
		int d=getDistance(i.y,f);
		p[i.y]=p[f]-d;
		if(p[i.y]<=p[y]){
			p[i.y]=p[z]+a[i.y];
			t[i.y]=2;
			v.pb(p[i.y]);
			f=i.y;
		}
		int c=*(lower_bound(v.begin(),v.end(),p[i.y]));
		if(a[i.y]==2*c-p[i.y]-p[z] && p[i.y]!=c){
			t[i.y]=1;
		}
		else{
			p[i.y]=p[z]+a[i.y];
			t[i.y]=2;
			v.pb(p[i.y]);
			f=i.y;
		}
	}
}

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