Submission #428623

#	Time	Username	Problem	Language	Result	Execution time	Memory
428623		jamezzz	Park (JOI17_park)	C++17	20 / 100	92 ms	592 KiB

park

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

#define sf scanf
#define pf printf
#define pb emplace_back
#define sz(x) (int)x.size()
mt19937 rng(time(0));

static int place[1400];
int rem[1405];

void dnc(int l,int r,vector<int> &v){
	/*
	pf("dnc: %d %d\n",l,r);
	for(int x:v)pf("%d ",x);
	pf("\n");
	//*/
	if(sz(v)==2){
		int _l=v[0],_r=v[1];
		if(_l>_r)swap(_l,_r);
		Answer(_l,_r);
		return;
	}
	int m=v[rng()%(sz(v)-2)+1];
	vector<int> nl,nr;
	nl.pb(l);
	nr.pb(m);
	memset(place,0,sizeof place);
	for(int i=0;i<sz(v);++i)place[v[i]]=1;
	for(int i=0;i<sz(v);++i){
		if(v[i]==l||v[i]==m||v[i]==r)continue;
		place[v[i]]=0;
		int _l=l,_m=m;
		if(_l>_m)swap(_l,_m);
		if(Ask(_l,_m,place)){
			nr.pb(v[i]);
			place[v[i]]=1;
		}
		else{
			nl.pb(v[i]);
			place[v[i]]=1;
		}
	}
	nl.pb(m);
	nr.pb(r);
	dnc(l,m,nl);
	dnc(m,r,nr);
}

void Detect(int T,int N){
	if(T==1){
		for(int i=0;i<N;++i)rem[i]=7;
		for(int i=0;i<N;++i){
			if(rem[i]==0)continue;
			for(int j=i+1;j<N;++j){
				if(rem[j]==0)continue;
				memset(place,0,sizeof place);
				place[i]=place[j]=1;
				if(Ask(i,j,place)){
					Answer(i,j);
					--rem[i];--rem[j];
				}
			}
		}
		return;
	}
	if(T==2){
		vector<int> v;
		for(int i=0;i<N;++i)v.pb(i);
		dnc(0,N-1,v);
	}
}

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