Submission #572606

#	Time	Username	Problem	Language	Result	Execution time	Memory
572606		Vanilla	Xylophone (JOI18_xylophone)	C++17	100 / 100	103 ms	460 KiB

xylophone

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

int a[5002];
int b[5002];
bool rel [5002];
int rs[5002];
int n;

bool check (bool sign) {
	rs[1] = 0;
	for (int i = 1; i < n; i++){
		if (sign == rel[i]) rs[i + 1] = rs[i] + a[i];
		else rs[i + 1] = rs[i] - a[i];
	}
	int k = *min_element(rs + 1, rs + n + 1);
	for (int i = 1; i <= n; i++){
		rs[i]-=k - 1;
	}
	if (min_element(rs + 1, rs + n + 1) > max_element(rs + 1, rs + n + 1)) return 0;
	return 1;
}

void solve(int N) {
	n = N;
	for (int i = 1; i < n; i++){
		a[i] = query(i, i + 1);
	}
	for (int i = 1; i < n - 1; i++){
		b[i] = query(i, i + 2);
		if (a[i] + a[i + 1] != b[i]) rel[i + 1] = !rel[i];
		else rel[i + 1] = rel[i];
	}
	if (!check(0)) check(1);
	for (int i = 1; i <= n; i++){
		answer(i, rs[i]);
	}
}

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