Submission #577678

#	Time	Username	Problem	Language	Result	Execution time	Memory
577678		Mazaalai	Rail (IOI14_rail)	C++17	0 / 100	92 ms	468 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define ALL(x) x.begin(),x.end()
using namespace std;
using PII = pair <int, int>;

// getDistance(int a, int b)
void findLocation(int n, int first, int location[], int stype[]) {
	// find closest;
	int d[2][n];
	int closest = 1, A = 0, B, C;
	for (int i = 1; i < n; i++) {
		d[0][i] = getDistance(A, i);
		if (d[0][i] < d[0][closest]) closest = i;
	}
	B = closest;
	int second = first + d[0][B];
	stype[A] = 1, location[A] = first;
	stype[B] = 2, location[B] = second;
	d[1][A] = d[0][B];
	for (int i = 1; i < n; i++) {
		if (i == B) continue;
		d[1][i] = getDistance(B, i);
	}
	vector <PII> left, right;
	int dist = d[0][B];
	for (int i = 1; i < n; i++) {
		if (i == B) continue;
		if (min(d[0][i], d[1][i]) < dist) {
			if (d[0][i] < d[1][i]) 
				stype[i] = 2, location[i] = first + d[0][i];
			else 
				stype[i] = 1, location[i] = second - d[1][i];
			continue;
		}
		if (d[0][i] < d[1][i]) right.pb({d[0][i], i});
		else left.pb({d[1][i], i});
	}
	sort(ALL(left));
	sort(ALL(right));
	// cout << "right: ";
	if (!right.empty()) {
		// for (auto el : right) cout << el.ss << ' ';
		int par = right[0].ss;
		stype[par] = 2, location[par] = first + d[0][par];
		for (int i = 1; i < right.size(); i++) {
			int dist, j; tie(dist, j) = right[i];
			int cur = getDistance(par, j);
			if (d[0][j] == d[0][par] + cur)
				stype[j] = 1, location[j] = location[par] - cur;
			else 
				stype[j] = 2, location[j] = A + d[0][j];

			if (d[0][j] == d[0][par] + cur) par = j;
		}
	}
	// cout << '\n';
	// cout << "left: ";
	if (!left.empty()) {
		// for (auto el : left) cout << el.ss << ' ';
		int par = left[0].ss;
		stype[par] = 2, location[par] = second - d[1][par];
		for (int i = 1; i < left.size(); i++) {
			int dist, j; tie(dist, j) = left[i];
			int cur = getDistance(par, j);
			if (d[1][j] == d[1][par] + cur)
				stype[j] = 2, location[j] = location[par] + cur;
			else 
				stype[j] = 1, location[j] = location[B] - d[1][j];

			if (d[1][j] == d[1][par] + cur) par = j;
		}
	}
	// cout << '\n';
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:49:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   for (int i = 1; i < right.size(); i++) {
      |                   ~~^~~~~~~~~~~~~~
rail.cpp:66:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |   for (int i = 1; i < left.size(); i++) {
      |                   ~~^~~~~~~~~~~~~
rail.cpp:14:29: warning: unused variable 'C' [-Wunused-variable]
   14 |  int closest = 1, A = 0, B, C;
      |                             ^

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