제출 #146734

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
146734		dolphingarlic	Xylophone (JOI18_xylophone)	C++14	0 / 100	2 ms	392 KiB

xylophone

#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
• Subtask 2: 0 / 36
• Subtask 3: 0 / 53