oj.uz

Submission #779511

# Submission time Handle Problem Language Result Execution time Memory
779511 2023-07-11T13:37:26 Z sadsa Xylophone (JOI18_xylophone) C++17
47 / 100
 288 ms 98656 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 q(int l, int r) {
	if (l > r) swap(l, r);

	int Q;

	if (l == r) Q = 0;
	else {
		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);
		if (r-l == 1) {
			if (q(r, N) == target) {
				l = r;
			} else {
				r = l;
			}
			break;
		}

		int mid = (l + r) / 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));

	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);

	for (int i = index1; i+2 <= N; ++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);
		DBG("next guess", ans[i0], ans[i1], ans[i2]);
		DBG("with info", q02, q12);
	}

	for (int i = index1+1; i-2 > 0; --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);
	}

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

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 6 ms 336 KB Output is correct
5 Correct 5 ms 336 KB Output is correct
6 Correct 7 ms 348 KB Output is correct
7 Correct 6 ms 336 KB Output is correct
8 Correct 7 ms 336 KB Output is correct
9 Correct 7 ms 336 KB Output is correct
10 Correct 6 ms 356 KB Output is correct
11 Correct 7 ms 336 KB Output is correct
12 Correct 5 ms 344 KB Output is correct
13 Correct 6 ms 336 KB Output is correct
14 Correct 9 ms 348 KB Output is correct
15 Correct 6 ms 336 KB Output is correct

Subtask #2
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 6 ms 336 KB Output is correct
5 Correct 5 ms 336 KB Output is correct
6 Correct 7 ms 348 KB Output is correct
7 Correct 6 ms 336 KB Output is correct
8 Correct 7 ms 336 KB Output is correct
9 Correct 7 ms 336 KB Output is correct
10 Correct 6 ms 356 KB Output is correct
11 Correct 7 ms 336 KB Output is correct
12 Correct 5 ms 344 KB Output is correct
13 Correct 6 ms 336 KB Output is correct
14 Correct 9 ms 348 KB Output is correct
15 Correct 6 ms 336 KB Output is correct
16 Correct 13 ms 536 KB Output is correct
17 Correct 39 ms 1232 KB Output is correct
18 Correct 49 ms 2992 KB Output is correct
19 Correct 58 ms 4300 KB Output is correct
20 Correct 55 ms 4292 KB Output is correct
21 Correct 47 ms 4304 KB Output is correct
22 Correct 75 ms 4284 KB Output is correct
23 Correct 69 ms 4340 KB Output is correct
24 Correct 33 ms 4288 KB Output is correct
25 Correct 50 ms 4308 KB Output is correct
26 Correct 67 ms 4312 KB Output is correct
27 Correct 43 ms 4304 KB Output is correct
28 Correct 67 ms 4296 KB Output is correct
29 Correct 59 ms 4300 KB Output is correct
30 Correct 60 ms 4284 KB Output is correct

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 6 ms 336 KB Output is correct
5 Correct 5 ms 336 KB Output is correct
6 Correct 7 ms 348 KB Output is correct
7 Correct 6 ms 336 KB Output is correct
8 Correct 7 ms 336 KB Output is correct
9 Correct 7 ms 336 KB Output is correct
10 Correct 6 ms 356 KB Output is correct
11 Correct 7 ms 336 KB Output is correct
12 Correct 5 ms 344 KB Output is correct
13 Correct 6 ms 336 KB Output is correct
14 Correct 9 ms 348 KB Output is correct
15 Correct 6 ms 336 KB Output is correct
16 Correct 13 ms 536 KB Output is correct
17 Correct 39 ms 1232 KB Output is correct
18 Correct 49 ms 2992 KB Output is correct
19 Correct 58 ms 4300 KB Output is correct
20 Correct 55 ms 4292 KB Output is correct
21 Correct 47 ms 4304 KB Output is correct
22 Correct 75 ms 4284 KB Output is correct
23 Correct 69 ms 4340 KB Output is correct
24 Correct 33 ms 4288 KB Output is correct
25 Correct 50 ms 4308 KB Output is correct
26 Correct 67 ms 4312 KB Output is correct
27 Correct 43 ms 4304 KB Output is correct
28 Correct 67 ms 4296 KB Output is correct
29 Correct 59 ms 4300 KB Output is correct
30 Correct 60 ms 4284 KB Output is correct
31 Correct 111 ms 19040 KB Output is correct
32 Correct 156 ms 38140 KB Output is correct
33 Correct 253 ms 75160 KB Output is correct
34 Incorrect 288 ms 98656 KB Wrong Answer [2]
35 Halted 0 ms 0 KB -