Submission #1185351

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185351		WH8	Park (JOI17_park)	C++20	0 / 100	223 ms	600 KiB

park

#include "park.h"
#include <bits/stdc++.h>
using namespace std;
static int Place[1400];

vector<int> par(1404,-1);

int n;

void path(int i){
	if(par[i]!=-1)return;
	//~ printf("enter path %d\n",i);
	int prv=0,ans=0;
	while (true){
		prv=ans;
		int hi=n-1, lo=0,m;
		int copy[1400];
		for(int j=0;j<1400;j++)copy[j]=Place[j];
		while(lo<=hi){
			m=(lo+hi)/2;
			for(int j=0;j<=m;j++)Place[j]=1;
			Place[0]=Place[i]=1;
			bool res=Ask(0, i, Place);
			for(int j=0;j<1400;j++)Place[j]=copy[j];
			//~ printf("when prefix is up to %d, res is %d\n",m,res);
			if(res){
				ans=m;
				hi=m-1;
			}
			else{
				lo=m+1;
			}
		}
		//~ printf("largest on path from %d to 0 is %d\n",i,ans);
		if(ans!=0){
			if(par[ans]==-1){
				for(int j=0;j<1400;j++)Place[j]=0;
				Place[0]=Place[ans]=1;
				path(ans);
			}
			int cur=ans;
			while(cur!=0 and cur!=1400){
				//~ cout<<cur<<" HERE\n";
				Place[cur]=1;
				cur=par[cur];
			}
		}
		else{
			par[i]=prv;
			break;
		}
	}
}

void Detect(int T, int N) {
	n=N;
	//~ printf("n is %lld\n", N);
	par[0]=0;
	for(int i=1;i<N;i++){
		for(int j=0;j<1400;j++)Place[j]=0;
		Place[i]=Place[0]=1;
		path(i);
	}
	//~ for(int i=1;i<N;i++){
		//~ printf("parent of %d is %d\n",i,par[i]);
	//~ }
	for(int i=1;i<N;i++){
		Answer(min(i,par[i]),max(i,par[i]));
	}
	//~ if(Ask(0, 4, Place) != 0) return;
}
/*
2
5 
4
0 3
3 4 
4 1 
1 2 
*/

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