Submission #1185998

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185998		WH8	Park (JOI17_park)	C++20	37 / 100	136 ms	8156 KiB

park

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

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

int n;

void path(int x, int y){
	if(x==y)return;
	if(par[x]!=-1 and par[y]!=-1)return; // the path from x to y is already found
	int place[1400]; 
	fill(place,place+1400,0);
	place[x]=1,place[y]=1;
	bool conn=Ask(min(x,y),max(x,y),place);
	if(conn){
		par[x]=y;
		return;
	}
	int hi=n-1, lo=0, ans=-1, m;
	while(hi>=lo){
		m=(hi+lo)/2;
		fill(place,place+1400,0);
		place[x]=1,place[y]=1;
		for(int i=0;i<=m;i++){
			place[i]=1;
		}
		int can=Ask(min(x,y),max(x,y),place);
		if(can){
			ans=m;
			hi=m-1;
		}
		else lo=m+1;
	}
	assert(ans!=-1);
	path(x, ans); 
	path(ans, y);
}

void Detect(int T, int N) {
	n=N;
	//~ printf("n is %lld\n", N);
	par[0]=0;
	for(int i=N-1;i>=1;i--){
		path(i, 0);
	}
	//~ 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 4
4 3 
3 2 
2 1
*/

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