Submission #418895

#	Time	Username	Problem	Language	Result	Execution time	Memory
418895		flappybird	Rail (IOI14_rail)	C++14	0 / 100	117 ms	492 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 (min(xdis[i], 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 (xdis[L[i]] > xdis[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]] = 2;
		ll a = 0;
		for (i = 1; i < L.size(); i++) {
			ll res = getDistance(L[a], L[i]);
			if (ydis[L[i]] = res + ydis[L[a]]) {
				location[L[i]] = location[L[a]] + res;
				stype[L[i]] = 2;
			}
			else {
				location[L[i]] = location[Y] - ydis[L[i]];
				stype[L[i]] = 1;
				a = i;
			}
		}
	}
	if (!R.empty()) {
		location[R[0]] = xdis[R[0]] + first;
		stype[R[0]] = 2;
		ll a = 0;
		for (i = 1; i < R.size(); i++) {
			ll res = getDistance(R[a], R[i]);
			if (xdis[R[i]] = res + xdis[R[a]]) {
				location[R[i]] = location[R[a]] - res;
				stype[R[i]] = 1;
			}
			else {
				location[R[i]] = first + xdis[R[i]];
				stype[R[i]] = 2;
				a = i;
			}
		}
	}
}

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 (xdis[L[i]] > xdis[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 (xdis[L[i]] > xdis[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:54:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |   for (i = 1; i < L.size(); i++) {
      |               ~~^~~~~~~~~~
rail.cpp:56:19: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   56 |    if (ydis[L[i]] = res + ydis[L[a]]) {
      |        ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
rail.cpp:71:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |   for (i = 1; i < R.size(); i++) {
      |               ~~^~~~~~~~~~
rail.cpp:73:19: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   73 |    if (xdis[R[i]] = res + xdis[R[a]]) {
      |        ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~

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