Submission #996007

#	Time	Username	Problem	Language	Result	Execution time	Memory
996007		BuzzyBeez	Xylophone (JOI18_xylophone)	C++17	0 / 100	0 ms	344 KiB

xylophone

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

int d[3][5008];
int a[5008];
bool mark[5008];

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

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[1][i] = query(i - 1, i), d[2][i] = 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: 0 / 11
• Subtask 2: 0 / 36
• Subtask 3: 0 / 53