제출 #200446

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
200446		Lawliet	철로 (IOI14_rail)	C++17	30 / 100	135 ms	98808 KiB

rail

#include <bits/stdc++.h>
#include "rail.h"

using namespace std;

const int MAXN = 5010;
typedef pair<int,int> pii;

int n;

int dist[MAXN][MAXN];

vector< pii > sweep;

int getDist(int A, int B)
{
	if( dist[A][B] == -1 )
		dist[A][B] = dist[B][A] = getDistance( A , B );

	return dist[A][B];
}

void findLocation(int N, int first, int location[], int stype[])
{
	int L = 0;

	memset( dist , -1 , sizeof(dist) );

	stype[L] = 1;
	location[L] = first;

	for(int i = 1 ; i < N ; i++)
		sweep.push_back( { getDist( 0 , i ) , i } );

	sort( sweep.begin() , sweep.end() );

	int R = sweep[0].second;

	stype[R] = 2;
	location[R] = first + getDist( L , R );

	for(int i = 1 ; i < sweep.size() ; i++)
	{
		int cur = sweep[i].second;

		int distL = getDist( L , cur );
		int distR = getDist( R , cur );

		if( distL == distR + getDist( L , R ) )
		{
			stype[cur] = 1;
			location[cur] = location[R] - distR;

			if( location[cur] < location[L] ) L = cur;
		}
		else
		{
			stype[cur] = 2;
			location[cur] = location[L] + distL;

			if( location[R] < location[cur] ) cur = R; 
		}
	}
}

컴파일 시 표준 에러 (stderr) 메시지

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:42:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 1 ; i < sweep.size() ; i++)
                  ~~^~~~~~~~~~~~~~

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