Submission #780741

#	Time	Username	Problem	Language	Result	Execution time	Memory
780741		JoenPoenMan	Xylophone (JOI18_xylophone)	C++17	47 / 100	87 ms	416 KiB

xylophone

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

using namespace std;
typedef pair<int, int> ii;

vector<ii> locations;

void findNext2(int N, int top, int bot, int prevLoc, bool gr1);

void findNext1(int N, int top, int bot = 1, int prevLoc = 1, bool gr1 = false, bool exl = false) {
	if (top == bot) return;
	int mid;
	int low = bot, high = top;
	int prev = query(low, high);
	if (abs(top - bot) != 1) {
		while (low != high) {
			mid = (low+high)/2;
			int res = query(bot, mid);
			if (res == prev) high = mid;
			else low = mid+1;
		}
	} else low = top;
	locations.push_back({prevLoc+prev*(gr1?-1:1), low});
	findNext1(N, top, low, prevLoc+prev*(gr1?-1:1), !gr1, true);
	findNext2(N, low, bot + exl, prevLoc+prev*(gr1?-1:1), !gr1);
}

void findNext2(int N, int top, int bot, int prevLoc = 1, bool gr1 = false ) {
	if (top == bot) return;
	int mid;
	int low = bot, high = top;
	int prev = query(low, high);
	if (abs(top - bot) != 1) {
		while (low != high) {
			mid = (low+high+1)/2;
			int res = query(mid, top);
			if (res == prev) low = mid;
			else high = mid-1;
		}
	} else low = bot;
	locations.push_back({prevLoc+prev*(gr1?-1:1), low});
	findNext1(N, top-1, low, prevLoc+prev*(gr1?-1:1), !gr1, true);
	findNext2(N, low, bot, prevLoc+prev*(gr1?-1:1), !gr1);
}

void solve(int N) {
	findNext1(N, N);
	for (int i = 0; i < N; i++) {
		answer(locations[i].second, locations[i].first);
	}
}

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