Submission #289950

#	Time	Username	Problem	Language	Result	Execution time	Memory
289950		tinjyu	Rail (IOI14_rail)	C++14	100 / 100	91 ms	7432 KiB

rail

#include "rail.h"
#include <iostream>
#include <algorithm>
using namespace std;
long long int tag[10000005],t[100005],n,map[5005][3],l[1000005],r[1000005],lcnt,rcnt;
bool cmp1(int a,int b)
{
	return map[a][1]<map[b][1];
}
bool cmp2(int a,int b)
{
	return map[a][0]<map[b][0];
}
void findLocation(int N, int first, int location[], int stype[])
{
	n=N;
	long long int mi=9999999999,ri=0;
	for(int i=1;i<n;i++)
	{
		map[i][0]=getDistance(0,i);
		if(map[i][0]<mi)
		{
			mi=map[i][0];
			ri=i;
		}
	}
	location[ri]=first+mi;
	location[0]=first;
	stype[0]=1;
	stype[ri]=2;
	for(int i=1;i<n;i++)
	{
		map[i][1]=getDistance(ri,i);
	}
	//cout<<ri<<endl;
	for(int i=1;i<n;i++)
	{
		if(ri==i || stype[i]!=0)continue;
		if(map[ri][0]+map[i][1]==map[i][0])
		{
			if(map[i][1]<=map[ri][0])
			{
				location[i]=location[ri]-map[i][1];
				stype[i]=1;
				continue;
			}
			lcnt++;
			l[lcnt]=i;
		}
		else
		{
			rcnt++;
			r[rcnt]=i;
		}
	}
	sort(l+1,l+lcnt+1,cmp1);
	sort(r+1,r+rcnt+1,cmp2);
	//for(int i=1;i<=lcnt;i++)cout<<l[i]<<" ";
	//cout<<endl;
	//for(int i=1;i<=rcnt;i++)cout<<r[i]<<" ";
	//cout<<endl;
	int p=0;
	for(int i=1;i<=lcnt;i++)
	{		

		if(p==0)
		{
			p++;
			t[p]=l[i];
			location[l[i]]=location[ri]-map[l[i]][1];
			stype[l[i]]=1;
			tag[location[l[i]]]=1;
		}
		else
		{
			long long int tmp=getDistance(t[p],l[i]);
			long long int datla=(map[t[p]][1]+tmp-map[l[i]][1])/2;
			if(tag[location[t[p]]+datla]==1 && location[t[p]]+datla<location[0])
			{
				location[l[i]]=location[t[p]]+tmp;
				stype[l[i]]=2;
				tag[location[l[i]]]=2;
			}
			else
			{
				p++;
				t[p]=l[i];
				location[l[i]]=location[ri]-map[l[i]][1];
				stype[l[i]]=1;
				tag[location[l[i]]]=1;
			}
		}
	}
	p=0;
	for(int i=1;i<=rcnt;i++)
	{
		if(p==0)
		{
			p++;
			t[p]=r[i];
			location[r[i]]=location[0]+map[r[i]][0];
			stype[r[i]]=2;
			tag[location[r[i]]]=2;
		}
		else
		{
			long long int tmp=getDistance(t[p],r[i]);
			long long int datla=(map[t[p]][0]+tmp-map[r[i]][0])/2;
			if(tag[location[t[p]]-datla]==2 && location[t[p]]-datla>ri)
			{
			
				location[r[i]]=location[t[p]]-tmp;
				stype[r[i]]=1;
				tag[location[l[i]]]=1;
			}
			else
			{
				p++;
				t[p]=r[i];
				location[r[i]]=location[0]+map[r[i]][0];
				stype[r[i]]=2;
				tag[location[r[i]]]=2;
			}
		}
	}
	//for(int i=0;i<n;i++)cout<<location[i]<<" ";
	//cout<<endl;
	//for(int i=0;i<n;i++)cout<<stype[i]<<" ";
	//cout<<endl;
}

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