Submission #399515

#	Time	Username	Problem	Language	Result	Execution time	Memory
399515		peuch	Rail (IOI14_rail)	C++17	100 / 100	102 ms	4476 KiB

rail

#include "rail.h"
#include<bits/stdc++.h>
using namespace std;

const int MAXN = 5e5 + 10;
const int MAXM = 1e6 + 10;

vector<int> esq, dir;
int dist[2][MAXN];
int id[MAXM];

bool cmp(int i, int j){
	return dist[0][i] < dist[0][j];
}

void findLocation(int N, int first, int location[], int stype[])
{
	int mini = 1e8, x = 0;
	for(int i = 1; i < N; i++){
		dist[0][i] = getDistance(0, i);
		if(dist[0][i] < mini) mini = dist[0][i], x = i;
	}
	
	memset(id, -1, sizeof(id));
	
	dist[1][0] = dist[0][x];
	location[x] = first + dist[1][0];
	id[location[x]] = x;
	stype[x] = 2;
	location[0] = first;
	id[location[0]] = 0;
	stype[0] = 1;
	
	for(int i = 1; i < N; i++){
		if(i == x) continue;
		dist[1][i] = getDistance(x, i);
		if(dist[1][i] + dist[0][x] == dist[0][i]){
			if(dist[1][i] < dist[0][x]){
				location[i] = location[x] - dist[1][i];
				stype[i] = 1;
				id[location[i]] = i;
			}
			else esq.push_back(i);
		}
		else
			dir.push_back(i);
	}
	
	sort(dir.begin(), dir.end(), cmp);
	sort(esq.begin(), esq.end(), cmp);
	
	int y = x;
	for(int i = 0; i < dir.size(); i++){
		int cur = dir[i];
		int aux = (y == x) ? dist[1][cur] : getDistance(y, cur);
		int d = (dist[0][y] + aux - dist[0][cur]) / 2;
		int j = location[y] - d;
		if(j >= 0 && id[j] != -1 && stype[id[j]] == 2){
			location[cur] = location[y] - aux;
			stype[cur] = 1;
			id[location[cur]] = cur;
		}
		else{
			location[cur] = location[0] + dist[0][cur];
			stype[cur] = 2;
			id[location[cur]] = cur;
			y = cur;
		}
	}
	
	y = 0;
	for(int i = 0; i < esq.size(); i++){
		int cur = esq[i];
		int aux = (y == 0) ? dist[0][cur] : getDistance(y, cur);
		int d = (dist[1][y] + aux - dist[1][cur]) / 2;
		int j = location[y] + d;
		if(j >= 0 && id[j] != -1 && stype[id[j]] == 1){
			location[cur] = location[y] + aux;
			stype[cur] = 2;
			id[location[cur]] = cur;
		}
		else{
			location[cur] = location[x] - dist[1][cur];
			stype[cur] = 1;
			id[location[cur]] = cur;
			y = cur;
		}
	}
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:53:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |  for(int i = 0; i < dir.size(); i++){
      |                 ~~^~~~~~~~~~~~
rail.cpp:72:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |  for(int i = 0; i < esq.size(); i++){
      |                 ~~^~~~~~~~~~~~

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