Submission #1311733

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311733		madamadam3	Xylophone (JOI18_xylophone)	C++20	0 / 100	1 ms	332 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>

using namespace std;

static int A[5000];

void solve(int N) {
	int value = query(1, N);
	int L = 1, R = N;
	
	int lo = 1, hi = N;
	while (lo < hi) {
		int mid = lo + (hi - lo) / 2;
		if (query(1, mid) == value) {
			hi = mid;
		} else {
			lo = mid + 1;
		}
	}

	R = lo;
	lo = 1, hi = N;
	while (lo < hi) {
		int mid = lo + (hi - lo + 1) / 2;
		if (query(mid, N) == value) {
			lo = mid;
		} else {
			hi = mid - 1;
		}
	}
	L = lo;

	cerr << "L: " << L << " R: " << R << "\n";

	vector<int> ans(N+1, -1);
	ans[L] = 1; ans[R] = N;
	for (int i = L+1; i < R; i++) {
		if (i == L+1) {
			ans[i] = 1 + query(L, i);
		} else {
			int dx = query(i-1, i), dy = query(i-2, i);
			int a = ans[i-1] + dx, b = ans[i-1] - dx;
			int x = ans[i-2], y = ans[i-1];

			if (a <= 1 || a >= N) ans[i] = b;
			else if (b <= 1 || b >= N) ans[i] = a;
			else if (x < y && dy == a-x) ans[i] = a;
			else if (x > y && dy == x-y) ans[i] = a;
			else if (x < y && dy == y-x) ans[i] = b;
			else if (x > y && dy == x-b) ans[i] = b;
		}
	}

	for (int i = L-1; i >= 1; i--) {
		if (i == L-1) {
			ans[i] = 1 + query(i, L);
		} else {
			int dx = query(i, i+1), dy = query(i, i+2);
			int a = ans[i+1] + dx, b = ans[i+1] - dx;
			int x = ans[i+2], y = ans[i+1];

			if (a <= 1 || a >= N) ans[i] = b;
			else if (b <= 1 || b >= N) ans[i] = a;
			else if (x < y && dy == a-x) ans[i] = a;
			else if (x > y && dy == x-y) ans[i] = a;
			else if (x < y && dy == y-x) ans[i] = b;
			else if (x > y && dy == x-b) ans[i] = b;
		}
	}

	for (int i = R+1; i <= N; i++) {
		if (i == R+1) {
			ans[i] = N - query(R, i);
		} else {
			int dx = query(i-1, i), dy = query(i-2, i);
			int a = ans[i-1] + dx, b = ans[i-1] - dx;
			int x = ans[i-2], y = ans[i-1];

			if (a <= 1 || a >= N) ans[i] = b;
			else if (b <= 1 || b >= N) ans[i] = a;
			else if (x < y && dy == a-x) ans[i] = a;
			else if (x > y && dy == x-y) ans[i] = a;
			else if (x < y && dy == y-x) ans[i] = b;
			else if (x > y && dy == x-b) ans[i] = b;
		}
	}

	// for (int i = 1; i <= N; i++) cerr << ans[i] << " ";
	// cerr << "\n";

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

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