제출 #711919

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
711919		rainboy	Xylophone (JOI18_xylophone)	C++17	100 / 100	101 ms	556 KiB

xylophone

#include "xylophone.h"

const int N = 5000;

int min(int a, int b) { return a < b ? a : b; }

int dd1[N], dd2[N], aa[N];

void solve(int n) {
	for (int i = 0; i + 1 < n; i++)
		dd1[i] = query(i + 1, i + 2);
	for (int i = 0; i + 2 < n; i++)
		dd2[i] = query(i + 1, i + 3);
	aa[0] = 0, aa[1] = dd1[0];
	for (int i = 0; i + 2 < n; i++)
		aa[i + 2] = (aa[i] < aa[i + 1]) == (dd2[i] == dd1[i] + dd1[i + 1]) ? aa[i + 1] + dd1[i + 1] : aa[i + 1] - dd1[i + 1];
	int a = 0;
	for (int i = 0; i < n; i++)
		a = min(a, aa[i]);
	for (int i = 0; i < n; i++)
		aa[i] -= a;
	bool rev = false;
	for (int i = 0; i < n; i++)
		if (aa[i] == n - 1) {
			rev = true;
			break;
		} else if (aa[i] == 0) {
			rev = false;
			break;
		}
	if (rev)
		for (int i = 0; i < n; i++)
			aa[i] = n - 1 - aa[i];
	for (int i = 0; i < n; i++)
		answer(i + 1, aa[i] + 1);
}

• Subtask 1: 11 / 11
• Subtask 2: 36 / 36
• Subtask 3: 53 / 53