Submission #1254265

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254265		MercubytheFirst	Xylophone (JOI18_xylophone)	C++20	100 / 100	32 ms	744 KiB

xylophone

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

void solve(int N) {
	const int n = N;
	if(N == 1) {
		answer(1, 1);
		return;
	}
	if(N == 2) {
		answer(1, 1);
		answer(2, 2);
		return;
	}
	using i2 = pair<int, int>;
	vector<int> a(n+1), pdif(n+1);
	set<i2> s;
	pdif[2] = query(1, 2);
	a[1] = 0;
	a[2] = pdif[2];
	s.insert({a[1], 1});
	s.insert({a[2], 2});
	for(int i = 3; i <= n; ++i) {
		const int q1 = pdif[i-1];
		const int q2 = pdif[i] = query(i-1, i);
		const int q3 = query(i-2, i);
		//cerr << i << " : " << q1 << ' ' << q2 << ' ' << q3 << " | " << pdif[i] << '\n';
		if(a[i-2] < a[i-1]) {
			if(q1 + q2 == q3) { // i-1 median, a[i] = a[i-1]+q2
				a[i] = a[i-1]+q2;
			}
			else if(q1 == q3) { // i median, a[i] = a[i-1]-q2
				a[i] = a[i-1]-q2;
			}
			else if(q2 == q3) { // i-2 median, a[i] = a[i-1]-q2
				a[i] = a[i-1]-q2;
			}
			else {
				assert(false);
			}
		}
		else {
			if(q1 + q2 == q3) { // i-1 median, a[i] = a[i-1]-q2
				a[i] = a[i-1]-q2;
			}
			else if(q1 == q3) { // i median, a[i] = a[i-1]+q2
				a[i] = a[i-1]+q2;
			}
			else if(q2 == q3){
				a[i] = a[i-1]+q2;
			}
			else {
				assert(false);
			}
		}
		s.insert({a[i], i});
	}
	int add = -begin(s)->first + 1;
	for(const auto &[x, y] : s) {
		//cerr << "(" << x << ", " << y << "); ";
	}//cerr << '\n';
	int pos1 = -1, posn = -1;
	for(int i = 1; i <= n; ++i) {
		a[i] += add;
		//cerr << a[i] << " \n"[i == n];
		if(a[i] == 1) { pos1 = i; }
		if(a[i] == n) { posn = i; }
	}
	if(pos1 > posn) {
		for(int i = 1; i <= n; ++i) {
			a[i] = n - a[i] + 1;
		}
	}
	for(int i = 1; i <= n; ++i) {
		answer(i, a[i]);
	}

}

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