oj.uz

Submission #778862

# Submission time Handle Problem Language Result Execution time Memory
778862 2023-07-10T22:09:29 Z sadsa Xylophone (JOI18_xylophone) C++17
0 / 100
 0 ms 208 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);
	if (l == r) return 0;
	if (qcache[l][r] != -1) return qcache[l][r];
	return qcache[l][r] = query(l, r);
}

int find_one(int N) {
	int l = 1;
	int r = N;

	int target = N-1;

	while (l != r) {
		//DBG(l, r);
		if (r-l == 1) {
			if (q(l, N) == target) {
				r = l;
			} else {
				l = r;
			}
			break;
		}

		int mid = (l + r) / 2;
		//DBG("mid", mid);

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

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

	int one_index = find_one(N);

	for (int i = 1; i <= N; ++i) {
		answer(i, 1+q(one_index, i));
	}
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -