Submission #379391

#	Time	Username	Problem	Language	Result	Execution time	Memory
379391		pavement	Xylophone (JOI18_xylophone)	C++17	100 / 100	144 ms	748 KiB

xylophone

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

int dif[5005], ans[5005], out[5005];

void solve(int N) {
	for (int i = 1; i < N; i++) dif[i] = query(i, i + 1);
	ans[2] = dif[1];
	for (int i = 1; i < N - 1; i++) {
		int x = query(i, i + 2);
		if (dif[i] + dif[i + 1] == x) {
			if (ans[i + 1] > ans[i]) ans[i + 2] = ans[i + 1] + dif[i + 1];
			else ans[i + 2] = ans[i + 1] - dif[i + 1];
		} else {
			if (ans[i + 1] < ans[i]) ans[i + 2] = ans[i + 1] + dif[i + 1];
			else ans[i + 2] = ans[i + 1] - dif[i + 1];
		}
	}
	int curs = 1e9, smal = -1, curm = -1e9, big = -1;
	for (int i = 1; i <= N; i++) {
		if (ans[i] < curs) {
			curs = ans[i];
			smal = i;
		}
		if (ans[i] > curm) {
			curm = ans[i];
			big = i;
		}
	}
	if (smal > big) {
		for (int i = 1; i <= N; i++) ans[i] = -ans[i];
		swap(smal, big);
	}
	out[1] = 1 - ans[smal];
	for (int i = 2; i <= N; i++)
		out[i] = out[1] + ans[i];
	for (int i = 1; i <= N; i++)
		answer(i, out[i]);
}

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