Submission #818121

#	Time	Username	Problem	Language	Result	Execution time	Memory
818121		vjudge1	Rail (IOI14_rail)	C++14	100 / 100	53 ms	4360 KiB

rail

#include<bits/stdc++.h>
#include "rail.h"
using namespace std;
int mi=0x3f3f3f3f;
int st[2][55555],d[55555][2],v[2222222],o,oo;
int cmp(int a,int b){
	return d[a][0]<d[b][0];
}
void findLocation(int n,int fi,int l[],int s[]){
	l[0]=fi;
	s[0]=v[l[0]]=1;
	if(n==1) return ;
	int id=0;
	for(int i=1;i<n;i++){
		d[i][0]=getDistance(0,i);
		if(d[i][0]<mi){
			mi=d[i][0];
			id=i;
		}
	}
	l[id]=l[0]+mi;
	s[id]=2;
	v[l[id]]=2;
	for(int i=1;i<n;i++){
		if(i==id) continue;
		d[i][1]=getDistance(i,id);
		if(d[i][1]+mi==d[i][0]){
			if(d[i][1]<mi){
				l[i]=l[id]-d[i][1];
				v[l[i]]=s[i]=1;
			}else{
				st[0][++o]=i;
			}
		}else{
			st[1][++oo]=i;
		}
	}
	sort(st[0]+1,st[0]+o+1,cmp);
	sort(st[1]+1,st[1]+oo+1,cmp);
	int la=0,now=0;
	for(int i=1;i<=o;i++){
		now=st[0][i];
		int len=(d[la][1]-d[now][1]+getDistance(la,now))/2;
		if(v[l[la]+len]==1){
			s[now]=2;
			l[now]=2*(l[la]+len)+d[now][1]-l[id];
		}else{
			la=now;
			s[now]=1;
			l[now]=l[id]-d[now][1];
		}
		v[l[now]]=s[now];
	}
	la=id;
	for(int i=1;i<=oo;i++){
		now=st[1][i];
		int len=(d[la][0]-d[now][0]+getDistance(la,now))/2;
		if(v[l[la]-len]==2){
			s[now]=1;
			l[now]=2*(l[la]-len)-d[now][0]-l[0];
		}else{
			la=now;
			s[now]=2;
			l[now]=l[0]+d[now][0];
		}
		v[l[now]]=s[now];
	}
}

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