Submission #63074

#	Time	Username	Problem	Language	Result	Execution time	Memory
63074		shoemakerjo	Xylophone (JOI18_xylophone)	C++14	100 / 100	85 ms	724 KiB

xylophone

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

bool taken[maxn];
int ans[maxn];

void solve(int N) {

	//call query on range s to t
	//call answer setting index i to a
	fill(taken, taken+maxn, false);

	int small = 1;
	for (int inc = (1 << 14); inc > 0; inc /= 2) {
		if (small + inc > N) continue;
		int nx = small + inc;
		int qu = query(nx, N);
		if (qu == N-1) {
			//did not go too far
			small = nx;
		}
	}
	// cout << "small: " << small << endl;
	ans[small] = 1;
	taken[1] = true;
	if (small != 1) {
		ans[small-1] = query(small-1, small)+1;
		taken[ans[small-1]] = true;
	}
	if (small != N) {
		ans[small+1] = query(small, small+1)+1;
		taken[ans[small-1]] = true;
	}
	for (int i = small-2; i >= 1; i--) {
		int nx = i+1;
		int nx2 = i+2;
		int q1 = query(i, nx); //reverse inputs for other direction

		int op1 = ans[nx] + q1; //is greater
		int op2 = ans[nx] - q1; //is less 
		if (taken[op1] || op1 < 1 || op1 > N) {
			ans[i] = op2;
			taken[op2] = true;
			continue;
		}
		if (taken[op2] || op2 < 1 || op2 > N) {
			ans[i] = op1;
			taken[op1] = true;
			continue;
		}

		int q2 = query(i, nx2);
		if (q2 == abs(ans[nx]-ans[nx2])) {
			//nothing changed (i am between them)
			if (ans[nx2] > ans[nx]) {
				ans[i] = op1;
				taken[op1] = true;
				continue;
			}
			else {
				ans[i] = op2;
				taken[op2] = true;
				continue;
			}
		}
		else {
			int mx = 0;
			mx = max(mx, abs(ans[nx2]-ans[nx]));
			mx = max(mx, abs(ans[nx]-op1));
			mx = max(mx, abs(ans[nx2]-op1));
			//something happened
			if (mx == q2) {
				ans[i] = op1;
				taken[op1] = true;

			}
			else {
				ans[i] = op2;
				taken[op2] = true;
			}
		}


	}
	for (int i = small+2; i <= N; i++) {
		int nx = i-1;
		int nx2 = i-2;

		int q1 = query(nx, i); //reverse inputs for other direction

		int op1 = ans[nx] + q1; //is greater
		int op2 = ans[nx] - q1; //is less 
		if (taken[op1] || op1 < 1 || op1 > N) {
			ans[i] = op2;
			taken[op2] = true;
			continue;
		}
		if (taken[op2] || op2 < 1 || op2 > N) {
			ans[i] = op1;
			taken[op1] = true;
			continue;
		}

		int q2 = query(nx2, i);
		if (q2 == abs(ans[nx]-ans[nx2])) {
			//nothing changed (i am between them)
			if (ans[nx2] > ans[nx]) {
				ans[i] = op1;
				taken[op1] = true;
				continue;
			}
			else {
				ans[i] = op2;
				taken[op2] = true;
				continue;
			}
		}
		else {
			int mx = 0;
			mx = max(mx, abs(ans[nx2]-ans[nx]));
			mx = max(mx, abs(ans[nx]-op1));
			mx = max(mx, abs(ans[nx2]-op1));
			//something happened
			if (mx == q2) {
				ans[i] = op1;
				taken[op1] = true;

			}
			else {
				ans[i] = op2;
				taken[op2] = true;
			}
		}

	}

	for (int i = 1; i <= N; i++) {
		// cout << "answering: " << i << ":    " << ans[i] << endl;
		answer(i, ans[i]);
	}



}

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