제출 #217947

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
217947		dorijanlendvaj	Park (JOI17_park)	C++14	77 / 100	188 ms	668 KiB

park

#include "park.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define pii pair<int,int>
#define pb push_back
#define eb emplace_back
#pragma GCC optimize("unroll-loops")
#define vi vector<int>
#define vl vector<ll>
#define all(a) begin(a),end(a)

using namespace std;
using ll=long long;
const char en='\n';

static int Place[1400];
int n,de[1400],par[1400];
vi im[1400],sv,cur;
bool bio[1400];

int rmq(int a,int b) //max
{
	int lo=-1,hi=n-1;
	while (lo<hi)
	{
		int mid=(lo+hi+2)/2-1;
		for (int i=0;i<=mid;++i) Place[i]=1;
		for (int i=mid+1;i<n;++i) Place[i]=0;
		Place[a]=1;
		Place[b]=1;
		if (Ask(min(a,b),max(a,b),Place)) hi=mid;
		else lo=mid+1;
	}
	return lo;
}

void cons(int l,int r)
{
	int a=rmq(l,r);
	if (a==-1) return;
	cons(l,a);
	cur.pb(a);
	cons(a,r);
}

mt19937 rng(177);

void Detect(int T, int N) {
	if (T==1)
	{
		for (int i=0;i<N;++i)
		{
			for (int j=i+1;j<N;++j)
			{
				Place[i]=Place[j]=1;
				if (Ask(i,j,Place)) Answer(i,j);
				Place[i]=Place[j]=0;
			}
		}
		return;
	}
	n=N;
	vi ord;
	for (int i=1;i<n;++i) ord.pb(i);
	shuffle(all(ord),rng);
	im[0].pb(0);
	bio[0]=1;
	sv.pb(0);
	int mad=0;
	for (auto i: ord)
	{
		if (bio[i]) continue;
		int lo=0,hi=mad;
		while (lo<hi)
		{
			int mid=(lo+hi+1)/2;
			for (int i=0;i<n;++i) Place[i]=1;
			for (auto a: sv) if (de[a]>=mid) Place[a]=0;
			if (Ask(0,i,Place)) hi=mid-1;
			else lo=mid;
		}
		int dd=lo;
		lo=0;
		hi=im[dd].size()-1;
		while (lo<hi)
		{
			int mid=(lo+hi)/2;
			for (int i=0;i<n;++i) Place[i]=1;
			for (int i=0;i<=mid;++i) Place[im[dd][i]]=0;
			if (Ask(0,i,Place)) lo=mid+1;
			else hi=mid;
		}
		int no=im[dd][lo];
		//cout<<i<<' '<<no<<endl;
		cur.clear();
		cur.pb(no);
		cons(no,i);
		cur.pb(i);
		for (int i=1;i<cur.size();++i)
		{
			par[cur[i]]=cur[i-1];
			de[cur[i]]=de[cur[i-1]]+1;
			im[de[cur[i]]].pb(cur[i]);
			bio[cur[i]]=1;
			sv.pb(cur[i]);
			mad=max(mad,de[cur[i]]);
			//cout<<cur[i]<<' '<<par[cur[i]]<<' '<<de[cur[i]]<<endl;
			Answer(min(cur[i-1],cur[i]),max(cur[i-1],cur[i]));
		}
	}
}

컴파일 시 표준 에러 (stderr) 메시지

park.cpp: In function 'void Detect(int, int)':
park.cpp:100:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=1;i<cur.size();++i)
                ~^~~~~~~~~~~

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