Submission #683976

#	Time	Username	Problem	Language	Result	Execution time	Memory
683976		rainboy	Park (JOI17_park)	C++17	77 / 100	321 ms	540 KiB

park

#include "park.h"
#include <string.h>

const int N = 1400;

int t, n;

int query(int *used, int a, int b) {
	int tmp;
	if (a > b)
		tmp = a, a = b, b = tmp;
	return Ask(a, b, used);
}

void answer(int a, int b) {
	int tmp;
	if (a > b)
		tmp = a, a = b, b = tmp;
	Answer(a, b);
}

void Detect(int t_, int n_) {
	t = t_, n = n_;
	if (t == 1) {
		static int used[N];
		for (int i = 0; i < n; i++)
			for (int j = i + 1; j < n; j++) {
				for (int k = 0; k < n; k++)
					used[k] = k == i || k == j ? 1 : 0;
				if (query(used, i, j))
					answer(i, j);
			}
	} else if (t <= 4) {
		static int ii[N], used[N];
		for (int j = 0; j < n; j++) {
			int lower = 0, upper = j;
			while (upper - lower > 1) {
				int h = (lower + upper) / 2;
				for (int i = 0; i < n; i++)
					used[i] = 1;
				for (int h_ = h; h_ < j; h_++)
					used[ii[h_]] = 0;
				if (query(used, 0, j))
					upper = h;
				else
					lower = h;
			}
			for (int h = j; h > upper; h--)
				ii[h] = ii[h - 1];
			ii[upper] = j;
		}
		for (int h = 1; h < n; h++) {
			int lower = -1, upper = h - 1;
			while (upper - lower > 1) {
				int g = (lower + upper) / 2;
				for (int i = 0; i < n; i++)
					used[i] = 0;
				for (int f = 0; f <= g; f++)
					used[ii[f]] = 1;
				used[ii[h]] = 1;
				if (query(used, 0, ii[h]))
					upper = g;
				else
					lower = g;
			}
			answer(ii[upper], ii[h]);
		}
	}
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 27 / 27
• Subtask 4: 30 / 30
• Subtask 5: 0 / 23