Submission #704229

#	Time	Username	Problem	Language	Result	Execution time	Memory
704229		TranGiaHuy1508	Xylophone (JOI18_xylophone)	C++17	100 / 100	66 ms	596 KiB

xylophone

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

#include "xylophone.h"

void solve(int N){
	int pos = 1;
	{
		int l = 1, r = N;
		while (r - l > 1){
			int mid = (l + r) >> 1;
			if (query(mid, N) == N-1) l = mid;
			else r = mid-1;
		}
		if (l != r){
			if (query(r, N) == N-1) pos = r;
			else pos = l;
		}
		else pos = l;
	}

	vector<int> res(N + 1, 0);
	set<int> alr;

	res[pos] = 1; alr.insert(1);

	for (int i = pos + 1; i <= N; i++){
		int diff = query(i - 1, i);
		vector<int> opts;
		for (int sign: {-1, 1}){
			int cand = res[i - 1] + sign * diff;
			if (1 <= cand && cand <= N && !alr.count(cand)) opts.push_back(cand);
		}

		if ((int)opts.size() == 1){
			res[i] = opts[0];
			alr.insert(res[i]);
		}
		else{
			int d2 = query(i - 2, i);
			for (int j = 0; j < (int)opts.size(); j++){
				if (d2 == max({res[i - 2], res[i - 1], opts[j]}) - min({res[i - 2], res[i - 1], opts[j]})){
					res[i] = opts[j];
					alr.insert(res[i]);
					break;
				}
			}
		}
	}

	for (int i = pos - 1; i >= 1; i--){
		int diff = query(i, i + 1);
		vector<int> opts;
		for (int sign: {-1, 1}){
			int cand = res[i + 1] + sign * diff;
			if (1 <= cand && cand <= N && !alr.count(cand)) opts.push_back(cand);
		}

		if ((int)opts.size() == 1){
			res[i] = opts[0];
			alr.insert(res[i]);
		}
		else{
			int d2 = query(i, i + 2);
			for (int j = 0; j < (int)opts.size(); j++){
				if (d2 == max({res[i + 2], res[i + 1], opts[j]}) - min({res[i + 2], res[i + 1], opts[j]})){
					res[i] = opts[j];
					alr.insert(res[i]);
					break;
				}
			}
		}
	}

	for (int i = 1; i <= N; i++) answer(i, res[i]);
}

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