제출 #14756

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
14756		progressive	철로 (IOI14_rail)	C++98	30 / 100	414 ms	99104 KiB

rail

#include "rail.h"
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

static int di[5010][5010];
static int d(int i,int j)
{
	if(!di[i][j]) di[j][i]=di[i][j]=getDistance(i,j);
	return di[i][j];
}

void findLocation(int N, int first, int location[], int stype[])
{
	memset(di,0,sizeof(di));
	const int Ctype=1;
	const int Dtype=2;
	
	for(int i=0;i<N;i++) stype[i]=0;
	stype[0]=Ctype;
	location[0]=0;
	//initialize, assume location of eki 0 is 0
	
	if(N==1) return; 
	
	vector< pair<int, int> > D0;
	for(int i=1;i<N;i++)
		D0.push_back(make_pair(d(0,i),i));
	sort(D0.begin(),D0.end());
	
	stype[D0[0].second]=Dtype;
	location[D0[0].second]=D0[0].first;
	
	for(int i=1;i<N-1;i++)
	{
		//get C, Dtypes min, max
		int Cmin=0,Dmax=D0[0].second;
		for(int j=0;j<N;j++)
		{
			if(stype[j]==Ctype)
				if(location[Cmin]>location[j])
					Cmin=j;
			if(stype[j]==Dtype)
				if(location[Dmax]<location[j])
					Dmax=j;
		}
		int Cdist=d(Cmin,D0[i].second);
		int Ddist=d(Dmax,D0[i].second);
		
		//Suppose Dtype
		
		int Tlocation=location[Cmin]+Cdist;
		//Target location,
		
		//find max Ctype less than Tlocation
		int Cmax=Cmin;
		for(int j=0;j<N;j++)
			if(stype[j]==Ctype)
				if(location[Cmax]<location[j] && location[Cmax]<Tlocation)
					Cmax=j;
		
		int EDdist=location[Dmax]-location[Cmax]+Tlocation-location[Cmax]; //Expected Distance of D
		if(Ddist==EDdist)
		{
			stype[D0[i].second]=Dtype;
			location[D0[i].second]=Tlocation; //Dtype
		}
		else
		{
			stype[D0[i].second]=Ctype;
			location[D0[i].second]=location[Dmax]-Ddist; //Ctype
		}
		
	}
	
	for(int i=0;i<N;i++)
		location[i]+=first; //add offset, location of eki 0 is first
	return;
	
}

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