Submission #1208953

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208953		mychecksedad	Park (JOI17_park)	C++20	10 / 100	363 ms	840 KiB

park

/* Author : Mychecksdead  */
#include "park.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;

static int Place[1400];

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int rn(int l, int r){
	return uniform_int_distribution<int>(l,r)(rng);
}
int n;
bool ask(int a, int b, vi u){
	for(int i = 0; i < n; ++i) Place[i] = 0;
	if(a > b) swap(a, b);
	Place[a] = 1;
	Place[b] = 1;
	for(int x: u) Place[x] = 1;
	return Ask(a, b, Place);
}
bool ask2(int a, int b, vi u){
	for(int i = 0; i < n; ++i) Place[i] = 1;
	for(int x: u) Place[x] = 0;
	if(a > b) swap(a, b);
	return Ask(a, b, Place);
}
void answer(int a, int b){
	if(a>b) swap(a, b);
	Answer(a, b);
}
void solve(vector<int> nodes){
	if(nodes.size() <= 1) return;
	int v = nodes[rn(0, int(nodes.size())-1)];
	vector<vi> C;
	vector<int> U;

	for(int u: nodes){
		if(u != v){
			bool is = ask(u, v, vi{});
			if(is){
				answer(u, v);
				C.pb(vi{u});
				U.pb(u);
			}
			// cerr << "dafuq\n";
		}
	}

	// cerr << v << ' ';
	// for(int u: U) cerr << u << ' ';
	// cerr << '\n';

	for(int u: nodes){
		bool is = 0;
		for(int x: U) is = is | (x == u);
		if(u != v && !is){
			int l = 0, r = int(U.size()) - 2, res = int(U.size()) - 1;
			while(l <= r){
				int mid = l+r>>1;
				vi to_pop;
				for(int i = 0; i <= mid; ++i) to_pop.pb(U[i]);
				if(ask2(v, u, to_pop) == 0){
					res = mid;
					r = mid - 1;
				}else{
					l = mid + 1;
				}
			}
			C[res].pb(u);
		}
	}
	for(auto V: C){
		solve(V);
	}
}

void Detect(int t, int nn) {
	n = nn;
	vi v; 
	for(int i = 1; i <= n; ++i){
		v.pb(i-1);
	}
	solve(v);
}

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