Submission #995946

#	Time	Username	Problem	Language	Result	Execution time	Memory
995946		12345678	Park (JOI17_park)	C++17	77 / 100	109 ms	856 KiB

park

#include "park.h"
#include <bits/stdc++.h>

using namespace std;

const int nx=1500;

static int Place[1400];

int n, pa[nx], used[nx], add[nx], l, r;
vector<int> d[nx], x;

void dfs(int u)
{
	x.push_back(u);
	for (auto v:d[u]) dfs(v);
}

void solve(int u)
{
	used[u]=1;
	for (int i=0; i<n; i++) Place[i]=used[i];
	if (Ask(0, u, Place)) return;
	int l=0, r=n-1;
	while (l<r)
	{
		int md=(l+r)/2;
		for (int i=0; i<n; i++) Place[i]=used[i];
		for (int i=0; i<=md; i++) Place[i]=1;
		if (Ask(0, u, Place)) r=md;
		else l=md+1;
	}
	pa[l]=pa[u];
	pa[u]=l;
	solve(l);
	solve(u);
}

void Detect(int T, int N) {
    if (N<=250)
    {
        for (int i=0; i<N; i++) 
        {
            Place[i]=1;
            for (int j=0; j<i; j++) 
            {
                Place[j]=1;
                if (Ask(j, i, Place)) Answer(j, i);
                Place[j]=0;
            }
            Place[i]=0;
        }
        return;
    }
	n=N;
	used[0]=add[0]=1;
	for (int i=1; i<N; i++) 
	{
		if (used[i]) continue;
		x.clear();
		dfs(0);
		l=0, r=x.size()-1;
		while (l<r)
		{
			int md=(l+r)/2;
			for (int j=0; j<N; j++) Place[j]=1;
			for (int j=md+1; j<x.size(); j++) Place[x[j]]=0;
			if (Ask(0, i, Place)) r=md;
			else l=md+1;
		}
		pa[i]=x[l];
		solve(i);
		int u=i;
		while (!add[u]) add[u]=1, d[pa[u]].push_back(u), u=pa[u];
	}
	//for (int i=1; i<N; i++) cout<<"pa "<<i<<' '<<pa[i]<<'\n';
	for (int i=1; i<N; i++) Answer(min(i, pa[i]), max(i, pa[i]));
}

Compilation message (stderr)

park.cpp: In function 'void Detect(int, int)':
park.cpp:67:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |    for (int j=md+1; j<x.size(); j++) Place[x[j]]=0;
      |                     ~^~~~~~~~~

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