제출 #470644

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
470644		Sohsoh84	Xylophone (JOI18_xylophone)	C++14	100 / 100	276 ms	576 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define debug(x)		cerr << #x << ": " << x << endl;
#define	sep 			' '

const ll MAXN = 5000 + 10;

int A[MAXN], n, B[MAXN], S[MAXN], P[MAXN];
bool C[MAXN];

bool final_ans() {
	int mn = *min_element(S + 1, S + n + 1);
	for (int i = 1; i <= n; i++) S[i] -= mn - 1, debug(S[i]);

	if (!is_permutation(S + 1, S + n + 1, P + 1, P + n + 1) || min_element(S + 1, S + n + 1) - max_element(S + 1, S + n + 1) >= 0) return false;
	for (int i = 1; i <= n; i++)
		answer(i, S[i]);
	
	return true;
}

void solve(int N) {
	n = N;
	for (int i = 1; i <= n; i++) P[i] = i;

	for (int i = 1; i < n; i++)
		B[i] = query(i, i + 1);
	for (int i = 1; i < n - 1; i++) {
		int x = query(i, i + 2);
		C[i + 1] = (x != B[i] + B[i + 1]);
	}

	S[1] = 1;

	bool b = true;
	for (int i = 2; i <= n; i++) {
		S[i] = S[i - 1] + (b ? 1 : -1) * B[i - 1];
		b ^= C[i];
	}

	if (!final_ans()) {
		bool b = false;
		for (int i = 2; i <= n; i++) {		
			S[i] = S[i - 1] + (b ? 1 : -1) * B[i - 1];
			b ^= C[i];
		}	

		final_ans();
	}
}

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