oj.uz

Submission #779534

# Submission time Handle Problem Language Result Execution time Memory
779534 2023-07-11T13:55:22 Z sadsa Xylophone (JOI18_xylophone) C++17
47 / 100
 268 ms 98612 KB 
#include "xylophone.h"

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

using ll = long long;
using vi = vector<int>;
using ii = tuple<int, int>;
using vii = vector<ii>;

constexpr int iINF = numeric_limits<int>::max();
constexpr ll lINF = numeric_limits<ll>::max();

template <typename T>
void DBG(T&& arg) {
    cerr << arg << '\n';
}

template <typename T, typename... Ts>
void DBG(T&& x, Ts&&... y) {
    cerr << x << ' ';
    DBG(y...);
}

static vector<vi> qcache;
int queries;

int q(int l, int r) {
	if (l > r) swap(l, r);

	int Q;

	if (l == r) Q = 0;
	else {
		if (qcache[l][r] == -1) queries++;
		Q = (qcache[l][r] != -1)? qcache[l][r]: (qcache[l][r] = query(l, r));
	}

	DBG("query:", l, r, "V:", Q);

	return Q;
}

int find_1(int N) {
	DBG("find_1=====================");
	int l = 1;
	int r = N-1;

	int target = N-1;

	while (l != r) {
		DBG("l,r", l, r);
		int mid = (l + r + 1) / 2;
		DBG("mid", mid);

		if (q(mid, N) == target) {
			l = mid;
		} else {
			r = mid-1;
		}
	}
	return l;
}

// finds a2
int get_next(int a0, int a1, int q02, int q12) {
	int a2;

	int q01 = abs(a1 - a0);

	if (q01 == q02) {
		DBG("WOOF");
		// minmax didnt change => ai2 between ai0 and ai1
		if (a0 < a1) a2 = a1 - q12;
		else a2 = a1 + q12;
	} else {
		DBG("MIAUW");
		if (a0 < a1) {
			if (q12 >= q02) a2 = a1 - q12;
			else a2 = a1 + q12;
		} else {
			if (q12 == q02) a2 = a1 + q12;
			else if (q12 < q02) a2 = a1 - q12;
			else a2 = a1 + q12;
		}
	}

	return a2;
}

void solve(int N) {
	qcache.clear();
	qcache.resize(N+1, vi(N+1, -1));
	queries = 0;

	int index1 = find_1(N);
	DBG("index 1:", index1);
	//int indexN = find_N(index1, N);
	//DBG("index N:", indexN);

	vi ans(N+1);
	ans[index1] = 1;

	ans[index1+1] = 1+q(index1, index1+1);

	bitset<5001> found;
	found[1] = 1;
	found[ans[index1+1]] = 1;

	for (int i = index1; i+2 <= N && found.count() < N-1; ++i) {
		DBG("starti", i);
		int i0=i;
		int i1=i+1;
		int i2=i+2;

		int q02 = q(i0, i2);
		int q12 = q(i1, i2);

		ans[i2] = get_next(ans[i0], ans[i1], q02, q12);
		found[ans[i2]] = 1;
		DBG("next guess", ans[i0], ans[i1], ans[i2]);
		DBG("with info", q02, q12);
	}

	for (int i = index1+1; i-2 > 0 && found.count() < N-1; --i) {
		int i0 = i;
		int i1 = i-1;
		int i2 = i-2;

		int q02 = q(i2, i);
		int q12 = q(i2, i1);

		ans[i2] = get_next(ans[i0], ans[i1], q02, q12);
		found[ans[i2]] = 1;
	}

	if (found.count() == N-1) {
		int missing_a;
		for (int i = 1; i <= N; ++i) {
			if (!found[i]) {
				missing_a = i;
				break;
			}
		}
		*find(ans.begin()+1, ans.end(), 0) = missing_a;
	}

	DBG(queries);
	for (int i = 1; i <= N; ++i) {
		answer(i, ans[i]);
	}
}

Compilation message

xylophone.cpp: In function 'void solve(int)':
xylophone.cpp:110:49: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  110 |  for (int i = index1; i+2 <= N && found.count() < N-1; ++i) {
      |                                   ~~~~~~~~~~~~~~^~~~~
xylophone.cpp:125:50: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  125 |  for (int i = index1+1; i-2 > 0 && found.count() < N-1; --i) {
      |                                    ~~~~~~~~~~~~~~^~~~~
xylophone.cpp:137:20: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  137 |  if (found.count() == N-1) {
      |      ~~~~~~~~~~~~~~^~~~~~
xylophone.cpp:145:38: warning: 'missing_a' may be used uninitialized in this function [-Wmaybe-uninitialized]
  145 |   *find(ans.begin()+1, ans.end(), 0) = missing_a;
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 3 ms 208 KB Output is correct
4 Correct 7 ms 336 KB Output is correct
5 Correct 4 ms 336 KB Output is correct
6 Correct 6 ms 348 KB Output is correct
7 Correct 6 ms 348 KB Output is correct
8 Correct 6 ms 348 KB Output is correct
9 Correct 8 ms 348 KB Output is correct
10 Correct 8 ms 348 KB Output is correct
11 Correct 6 ms 344 KB Output is correct
12 Correct 7 ms 336 KB Output is correct
13 Correct 7 ms 352 KB Output is correct
14 Correct 6 ms 348 KB Output is correct
15 Correct 8 ms 336 KB Output is correct

Subtask #2
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 3 ms 208 KB Output is correct
4 Correct 7 ms 336 KB Output is correct
5 Correct 4 ms 336 KB Output is correct
6 Correct 6 ms 348 KB Output is correct
7 Correct 6 ms 348 KB Output is correct
8 Correct 6 ms 348 KB Output is correct
9 Correct 8 ms 348 KB Output is correct
10 Correct 8 ms 348 KB Output is correct
11 Correct 6 ms 344 KB Output is correct
12 Correct 7 ms 336 KB Output is correct
13 Correct 7 ms 352 KB Output is correct
14 Correct 6 ms 348 KB Output is correct
15 Correct 8 ms 336 KB Output is correct
16 Correct 12 ms 576 KB Output is correct
17 Correct 33 ms 1248 KB Output is correct
18 Correct 46 ms 2984 KB Output is correct
19 Correct 71 ms 4280 KB Output is correct
20 Correct 56 ms 4296 KB Output is correct
21 Correct 63 ms 4288 KB Output is correct
22 Correct 71 ms 4272 KB Output is correct
23 Correct 59 ms 4260 KB Output is correct
24 Correct 43 ms 4280 KB Output is correct
25 Correct 62 ms 4316 KB Output is correct
26 Correct 54 ms 4320 KB Output is correct
27 Correct 54 ms 4264 KB Output is correct
28 Correct 58 ms 4256 KB Output is correct
29 Correct 49 ms 4284 KB Output is correct
30 Correct 57 ms 4304 KB Output is correct

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 3 ms 208 KB Output is correct
4 Correct 7 ms 336 KB Output is correct
5 Correct 4 ms 336 KB Output is correct
6 Correct 6 ms 348 KB Output is correct
7 Correct 6 ms 348 KB Output is correct
8 Correct 6 ms 348 KB Output is correct
9 Correct 8 ms 348 KB Output is correct
10 Correct 8 ms 348 KB Output is correct
11 Correct 6 ms 344 KB Output is correct
12 Correct 7 ms 336 KB Output is correct
13 Correct 7 ms 352 KB Output is correct
14 Correct 6 ms 348 KB Output is correct
15 Correct 8 ms 336 KB Output is correct
16 Correct 12 ms 576 KB Output is correct
17 Correct 33 ms 1248 KB Output is correct
18 Correct 46 ms 2984 KB Output is correct
19 Correct 71 ms 4280 KB Output is correct
20 Correct 56 ms 4296 KB Output is correct
21 Correct 63 ms 4288 KB Output is correct
22 Correct 71 ms 4272 KB Output is correct
23 Correct 59 ms 4260 KB Output is correct
24 Correct 43 ms 4280 KB Output is correct
25 Correct 62 ms 4316 KB Output is correct
26 Correct 54 ms 4320 KB Output is correct
27 Correct 54 ms 4264 KB Output is correct
28 Correct 58 ms 4256 KB Output is correct
29 Correct 49 ms 4284 KB Output is correct
30 Correct 57 ms 4304 KB Output is correct
31 Correct 128 ms 18900 KB Output is correct
32 Correct 177 ms 38016 KB Output is correct
33 Correct 254 ms 75092 KB Output is correct
34 Incorrect 268 ms 98612 KB Wrong Answer [2]
35 Halted 0 ms 0 KB -