Submission #1234675

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234675		PenguinsAreCute	Park (JOI17_park)	C++17	67 / 100	331 ms	668 KiB

park

#include "park.h"
#include <bits/stdc++.h>
using namespace std;
void Detect(int T, int N) {
	mt19937 rng(69);
	auto dnc = [&rng,N](auto &self, vector<int> loc, int st, int nd) -> vector<int> {
		if(loc.empty()) {
			Answer(min(st,nd), max(st,nd));
			return {nd};
		}
		int x = loc[rng() % loc.size()];
		vector<int> a, b;
		for(auto i: loc) if(i != x) {
			int place[N];
			fill(place,place+N,1);
			place[i] = 0;
			if(Ask(min(st,x), max(st,x), place))
				b.push_back(i);
			else
				a.push_back(i);
		}
		vector<int> lft = self(self, a, st, x);
		vector<int> rgt = self(self, b, x, nd);
		for(auto i: rgt)
			lft.push_back(i);
		return lft;
	};
	int vis[N];
	memset(vis,0,sizeof(vis));
	vis[0] = 1;
	vector<int> discover = {0};
	for(int i=1;i<N;i++)
		if(!vis[i]) {
			vis[i] = 1;
			vector<int> cur;
			while(!Ask(0,i,vis)) {
				int l = 0, h = N - 1;
				while(h - l > 1) {
					int m = (l + h) / 2;
					int place[N];
					fill(place,place+N,1);
					for(int j=0;j<=m;j++)
						if(!vis[j])
							place[j] = 0;
					if(!Ask(0,i,place))
						h = m;
					else
						l = m;
				}
				vis[h] = 1;
				cur.push_back(h);
			}
			int l = 0, h = discover.size();
			while(h - l > 1) {
				int m = (l + h) / 2;
				int place[N];
				fill(place,place+N,1);
				for(int j=m;j<discover.size();j++)
					place[discover[j]] = 0;
				if(!Ask(0,i,place))
					l = m;
				else
					h = m;
			}
			l = discover[l];
			vector<int> nw = dnc(dnc, cur, l, i);
			for(auto j: nw)
				discover.push_back(j);
		}
}

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