Submission #428501

#	Time	Username	Problem	Language	Result	Execution time	Memory
428501		pavement	Park (JOI17_park)	C++17	0 / 100	363 ms	508 KiB

park

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

#define mp make_pair
#define pb push_back

static int Place[1405];
static bool vis[1405];
map<pair<int, int>, vector<int> > rev;
vector<int> tmp;

void dfs(int n, int a, int b) {
	vis[n] = 1;
	for (auto i : rev[mp(a, b)]) {
		if (vis[i]) continue;
		Place[i] = 1;
		if (Ask(0, i, Place)) {
			i >= n ? Answer(n, i) : Answer(i, n);
			dfs(i, min(i, a), max(i, b));
		}
		Place[i] = 0;
	}
}

void Detect(int T, int N) {
	for (int i = 1; i < N; i++) {
		int lo = 0, hi = N - 1, ans = -1;
		while (lo <= hi) {
			int mid = (lo + hi) / 2;
			memset(Place, 0, sizeof Place);
			Place[0] = Place[i] = 1;
			for (int j = 1; j <= mid; j++) Place[j] = 1;
			if (Ask(0, i, Place)) ans = mid, hi = mid - 1;
			else lo = mid + 1;
		}
		if (ans == 0) {
			Answer(0, i);
			tmp.pb(i);
			continue;
		}
		lo = 0, hi = N - 1;
		int ans2 = -1;
		while (lo <= hi) {
			int mid = (lo + hi) / 2;
			memset(Place, 0, sizeof Place);
			Place[0] = Place[i] = 1;
			for (int j = mid; j < N; j++) Place[j] = 1;
			if (Ask(0, i, Place)) ans2 = mid, lo = mid + 1;
			else hi = mid - 1;
		}
		rev[mp(ans2, ans)].pb(i);
	}
	Place[0] = 1;
	vis[0] = 1;
	for (int i : tmp) {
		Place[i] = 1;
		dfs(i, i, i);
		Place[i] = 0;
	}
}

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