oj.uz

Submission #424784

# Submission time Handle Problem Language Result Execution time Memory
424784 2021-06-12T10:08:09 Z flappybird Rail (IOI14_rail) C++14
100 / 100
 146 ms 588 KB 
#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 460 KB Output is correct
2 Correct 117 ms 460 KB Output is correct
3 Correct 128 ms 460 KB Output is correct
4 Correct 113 ms 544 KB Output is correct
5 Correct 121 ms 460 KB Output is correct
6 Correct 146 ms 580 KB Output is correct
7 Correct 129 ms 516 KB Output is correct
8 Correct 110 ms 460 KB Output is correct
9 Correct 134 ms 460 KB Output is correct
10 Correct 111 ms 460 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 588 KB Output is correct
2 Correct 125 ms 460 KB Output is correct
3 Correct 122 ms 544 KB Output is correct
4 Correct 114 ms 460 KB Output is correct
5 Correct 133 ms 544 KB Output is correct
6 Correct 137 ms 540 KB Output is correct
7 Correct 126 ms 464 KB Output is correct
8 Correct 113 ms 468 KB Output is correct
9 Correct 112 ms 460 KB Output is correct
10 Correct 116 ms 464 KB Output is correct
11 Correct 145 ms 460 KB Output is correct
12 Correct 142 ms 460 KB Output is correct
13 Correct 117 ms 460 KB Output is correct
14 Correct 125 ms 460 KB Output is correct
15 Correct 116 ms 460 KB Output is correct
16 Correct 117 ms 468 KB Output is correct
17 Correct 130 ms 496 KB Output is correct
18 Correct 122 ms 512 KB Output is correct
19 Correct 120 ms 460 KB Output is correct
20 Correct 125 ms 460 KB Output is correct