Submission #996016

#	Time	Username	Problem	Language	Result	Execution time	Memory
996016		BuzzyBeez	Xylophone (JOI18_xylophone)	C++17	100 / 100	162 ms	1216 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;

int d[5008][3];
int a[5008];
int pos[5008];

bool check(int n) {
	fill(pos + 1, pos + n + 1, 0);
	for (int i = 1; i <= n; ++i)
		if (a[i] <= 0 || a[i] > n) return 0;
		else pos[a[i]] = i;
	for (int i = 1; i <= n; ++i) if (!pos[i]) return 0;
	return pos[1] < pos[n];
}

void deduce(int n) {
	for (int i = 3; i <= n; ++i) {
		if (a[i - 2] > a[i - 1]) {
			if (a[i - 2] - a[i - 1] + d[i][1] == d[i][2]) a[i] = a[i - 1] - d[i][1];
			else a[i] = a[i - 1] + d[i][1];
		}
		else {
			if (a[i - 1] - a[i - 2] + d[i][1] == d[i][2]) a[i] = a[i - 1] + d[i][1];
			else a[i] = a[i - 1] - d[i][1];
		}
	}
}

void return_answer(int n) {for (int i = 1; i <= n; ++i) answer(i, a[i]);}

void solve(int n) {
	for (int i = 3; i <= n; ++i) d[i][1] = query(i - 1, i), d[i][2] = query(i - 2, i);
	int d12 = query(1, 2);
	for (a[1] = 1; a[1] <= n; ++a[1]) {
		a[2] = a[1] + d12; deduce(n);
		if (check(n)) {return_answer(n); return;}
		a[2] = a[1] - d12; deduce(n);
		if (check(n)) {return_answer(n); return;}		
	}
}

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