Submission #424784

#	Time	Username	Problem	Language	Result	Execution time	Memory
424784		flappybird	Rail (IOI14_rail)	C++14	100 / 100	146 ms	588 KiB

rail

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

using namespace std;
typedef int ll;

#define MAX 5101
#define ln '\n'

ll xdis[MAX];
ll ydis[MAX];

ll Y;

void findLocation(int N, int first, int location[], int stype[]) {
	if (N == 1) {
		location[0] = first;
		stype[0] = 1;
		return;
	}
	ll i;
	ll mn = 200000000;
	for (i = 1; i < N; i++) {
		xdis[i] = getDistance(0, i);
		if (mn > xdis[i]) mn = xdis[i], Y = i;
	}
	ll d = ydis[0] = xdis[Y];
	location[0] = first;
	location[Y] = d + first;
	stype[0] = 1;
	stype[Y] = 2;
	for (i = 1; i < N; i++) if (i != Y) ydis[i] = getDistance(Y, i);
	vector<ll> L, R;
	for (i = 1; i < N; i++) {
		if (i == Y) continue;
		//i is in [0, Y]
		if ((xdis[i] == ydis[i] + d) && (ydis[i] < d)) {
			stype[i] = 1;
			location[i] = location[Y] - ydis[i];
		}
		else {
			if (xdis[i] == d + ydis[i]) L.push_back(i);
			else R.push_back(i);
		}
	}
	ll j;
	// bubble sort ( N <= 5000 blobaww )
	for (i = 0; i < L.size(); i++) for (j = i + 1; j < L.size(); j++) if (ydis[L[i]] > ydis[L[j]]) swap(L[i], L[j]);
	for (i = 0; i < R.size(); i++) for (j = i + 1; j < R.size(); j++) if (xdis[R[i]] > xdis[R[j]]) swap(R[i], R[j]);
	if (!L.empty()) {
		location[L[0]] = location[Y] - ydis[L[0]];
		stype[L[0]] = 1;
		ll a = 0;
		vector<ll> v;
		v.push_back(a);
		for (i = 1; i < L.size(); i++) {
			bool c = true;
			ll res = getDistance(L[a], L[i]);
			ll loc = location[L[a]] + res;
			ll asdf = -1;
			for (auto x : v) {
				if (loc > location[L[x]]) {
					asdf = x;
					break;
				}
			}
			ll x = asdf;
			if (asdf != -1 && ydis[L[i]] == ((location[Y] - location[L[x]]) + (loc - location[L[x]]))) c = false;
			if (c) {
				location[L[i]] = location[Y] - ydis[L[i]];
				stype[L[i]] = 1;
				a = i;
				v.push_back(a);
			}
			else {
				location[L[i]] = loc;
				stype[L[i]] = 2;
			}
		}
	}
	if (!R.empty()) {
		location[R[0]] = xdis[R[0]] + first;
		stype[R[0]] = 2;
		ll a = 0;
		vector<ll> v;
		v.push_back(a);
		for (i = 1; i < R.size(); i++) {
			bool c = true;
			ll res = getDistance(R[a], R[i]);
			//location of R[i] if stype[R[i]]=0
			ll loc = location[R[a]] - res;
			ll asdf = -1;
			for (auto x : v) {
				if (location[R[x]] > loc) {
					asdf = x;
					break;
				}
			}
			ll x = asdf;
			if (asdf != -1 && xdis[R[i]] == ((location[R[x]] - first) + (location[R[x]] - loc))) c = false;
			if (c) {
				location[R[i]] = first + xdis[R[i]];
				stype[R[i]] = 2;
				a = i;
				v.push_back(a);
			}
			else {
				location[R[i]] = loc;
				stype[R[i]] = 1;
			}
		}
	}
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:48:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  for (i = 0; i < L.size(); i++) for (j = i + 1; j < L.size(); j++) if (ydis[L[i]] > ydis[L[j]]) swap(L[i], L[j]);
      |              ~~^~~~~~~~~~
rail.cpp:48:51: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  for (i = 0; i < L.size(); i++) for (j = i + 1; j < L.size(); j++) if (ydis[L[i]] > ydis[L[j]]) swap(L[i], L[j]);
      |                                                 ~~^~~~~~~~~~
rail.cpp:49:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  for (i = 0; i < R.size(); i++) for (j = i + 1; j < R.size(); j++) if (xdis[R[i]] > xdis[R[j]]) swap(R[i], R[j]);
      |              ~~^~~~~~~~~~
rail.cpp:49:51: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  for (i = 0; i < R.size(); i++) for (j = i + 1; j < R.size(); j++) if (xdis[R[i]] > xdis[R[j]]) swap(R[i], R[j]);
      |                                                 ~~^~~~~~~~~~
rail.cpp:56:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |   for (i = 1; i < L.size(); i++) {
      |               ~~^~~~~~~~~~
rail.cpp:87:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |   for (i = 1; i < R.size(); i++) {
      |               ~~^~~~~~~~~~

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