oj.uz

답안 #14755

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
14755 2015-06-21T11:59:10 Z progressive 철로 (IOI14_rail) C++
30 / 100
 334 ms 99100 KB 
#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[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.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 86 ms 98564 KB Output is correct
2 Correct 81 ms 98564 KB Output is correct
3 Correct 87 ms 98696 KB Output is correct
4 Correct 76 ms 98696 KB Output is correct
5 Correct 79 ms 98696 KB Output is correct
6 Correct 90 ms 98752 KB Output is correct
7 Correct 76 ms 98796 KB Output is correct
8 Correct 72 ms 98796 KB Output is correct
9 Correct 70 ms 98796 KB Output is correct
10 Correct 70 ms 98796 KB Output is correct

Subtask #2
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 98796 KB Output is correct
2 Correct 70 ms 98804 KB Output is correct
3 Correct 77 ms 98804 KB Output is correct
4 Correct 66 ms 98812 KB Output is correct
5 Correct 72 ms 98812 KB Output is correct
6 Correct 72 ms 98812 KB Output is correct
7 Correct 74 ms 98816 KB Output is correct
8 Correct 69 ms 98816 KB Output is correct
9 Correct 94 ms 98816 KB Output is correct
10 Correct 71 ms 98816 KB Output is correct

Subtask #3
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 330 ms 99096 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 334 ms 99100 KB Output isn't correct
2 Halted 0 ms 0 KB -