Submission #102472

#	Time	Username	Problem	Language	Result	Execution time	Memory
102472		DrumpfTheGodEmperor	Xylophone (JOI18_xylophone)	C++14	100 / 100	92 ms	448 KiB

xylophone

#include <bits/stdc++.h>
#include "xylophone.h"
#define bp __builtin_popcountll
#define pb push_back
#define in(s) freopen(s, "r", stdin);
#define inout(s, end1, end2) freopen((string(s) + "." + end1).c_str(), "r", stdin),\
		freopen((string(s) + "." + end2).c_str(), "w", stdout);
#define fi first
#define se second
#define bw(i, r, l) for (int i = r - 1; i >= l; i--)
#define fw(i, l, r) for (int i = l; i < r; i++)
#define fa(i, x) for (auto i: x)
using namespace std;
const int mod = 1e9 + 7, inf = 1061109567;
const long long infll = 4557430888798830399;
const int N = 5005;
int res[N], a[N];
bool bigger[N];
int ask(int l, int r) { return query(l + 1, r + 1); }
void ans(int i, int a) { answer(i + 1, a); }
void solve(int n) {
	//bigger[i] = 1 if a[i] > a[i + 1]
	bigger[0] = 0;
	res[0] = ask(0, 1);
	fw (i, 1, n - 1) {
		int tmp1 = ask(i, i + 1), tmp2 = ask(i - 1, i + 1);
		res[i] = tmp1;
		if (tmp2 != tmp1 && tmp2 != res[i - 1]) {
			if (bigger[i - 1]) bigger[i] = 1;
			else bigger[i] = 0;
		} else {
			if (bigger[i - 1]) bigger[i] = 0;
			else bigger[i] = 1;
		}
	}
	int plusmx = 0, delmx = 0, plusmxpos = -1, delmxpos = -1;
	int cur = 0;
	fw (i, 0, n - 1) {
		if (bigger[i]) cur -= res[i];
		else cur += res[i];
		if (cur > plusmx) {
			plusmx = cur;
			plusmxpos = i;
		}
		if (cur < delmx) {
			delmx = cur;
			delmxpos = i;
		}
	}
	if (delmxpos > plusmxpos) {
		fw (i, 0, n - 1) bigger[i] ^= 1;
	}
	a[0] = 0;
	fw (i, 0, n - 1) {
		if (bigger[i]) a[i + 1] = a[i] - res[i];
		else a[i + 1] = a[i] + res[i];
	}
	int mnval = 0;
	fw (i, 1, n) mnval = min(mnval, a[i]);
	int offset = -mnval + 1;
	fw (i, 0, n) ans(i, a[i] + offset);
}

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