oj.uz

Submission #146734

# Submission time Handle Problem Language Result Execution time Memory
146734 2019-08-25T18:53:03 Z dolphingarlic Xylophone (JOI18_xylophone) C++14
0 / 100
 2 ms 392 KB 
#include "xylophone.h"

int A[5001];
bool visited[5001];

void solve(int N) {
	int l = 1, r = N;
	while (l != r) {
		int mid = (l + r + 1) / 2;
		if (query(mid, N) == N - 1) l = mid;
		else r = mid - 1;
	}

	A[l] = 1;
	visited[1] = true;

	if (l < N) {
		int q1 = query(l, l + 1);
		A[l + 1] = q1 + 1;
		visited[q1 + 1] = true;
		for (int i = l + 2; i <= N; i++) {
			q1 = query(i - 1, i);
			if (q1 + A[i - 1] > N || visited[q1 + A[i - 1]]) {
				A[i] = A[i - 1] - q1;
				visited[A[i - 1] - q1] = true;
			} else if (A[i - 1] - q1 < 1 || visited[A[i - 1] - q1]) {
				A[i] = A[i - 1] + q1;
				visited[A[i - 1] + q1] = true;
			} else {
				int q2 = query(i - 2, i);
				if (q2 == A[i - 2] - A[i - 1]) {
					A[i] = A[i - 1] + q1;
					visited[A[i - 1] + q1] = true;
				} else {
					A[i] = A[i - 1] - q1;
					visited[A[i - 1] - q1] = true;
				}
			}
		}
	}

	if (l > 1) {
		int q1 = query(l - 1, l);
		A[l - 1] = q1 + 1;
		for (int i = l - 2; i; i--) {
			q1 = query(i, i + 1);
			if (q1 + A[i + 1] > N || visited[q1 + A[i + 1]]) {
				A[i] = A[i + 1] - q1;
				visited[A[i + 1] - q1] = true;
			} else if (A[i + 1] - q1 < 1 || visited[A[i + 1] - q1]) {
				A[i] = A[i + 1] + q1;
				visited[A[i + 1] + q1] = true;
			} else {
				int q2 = query(i, i + 2);
				if (q2 == A[i + 2] - A[i + 1]) {
					A[i] = A[i + 1] + q1;
					visited[A[i + 1] + q1] = true;
				} else {
					A[i] = A[i + 1] - q1;
					visited[A[i + 1] - q1] = true;
				}
			}
		}
	}

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

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 392 KB Output is correct
2 Correct 2 ms 244 KB Output is correct
3 Incorrect 2 ms 248 KB Wrong Answer [4
4 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 392 KB Output is correct
2 Correct 2 ms 244 KB Output is correct
3 Incorrect 2 ms 248 KB Wrong Answer [4
4 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 392 KB Output is correct
2 Correct 2 ms 244 KB Output is correct
3 Incorrect 2 ms 248 KB Wrong Answer [4
4 Halted 0 ms 0 KB -