oj.uz

Submission #14754

# Submission time Handle Problem Language Result Execution time Memory
14754 2015-06-21T11:57:12 Z progressive Rail (IOI14_rail) C++
8 / 100
 349 ms 99092 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]=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

# Verdict Execution time Memory Grader output
1 Correct 73 ms 98516 KB Output is correct
2 Correct 76 ms 98612 KB Output is correct
3 Correct 76 ms 98676 KB Output is correct
4 Correct 77 ms 98772 KB Output is correct
5 Correct 78 ms 98848 KB Output is correct
6 Correct 80 ms 98848 KB Output is correct
7 Correct 76 ms 98848 KB Output is correct
8 Correct 74 ms 98864 KB Output is correct
9 Correct 87 ms 98864 KB Output is correct
10 Correct 98 ms 98864 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 71 ms 98864 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 330 ms 99004 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 349 ms 99092 KB Output isn't correct
2 Halted 0 ms 0 KB -