제출 #1282333

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1282333		Faisal_Saqib	동굴 (IOI13_cave)	C++20	100 / 100	122 ms	532 KiB

cave

#include "cave.h"
#include <vector>
#include <map>
#include <iostream>
using namespace std;
int d;
vector<int> cur,sp,fix;
int prv=-1;
// map<vector<int>,int> bf;
// int ASK(vector<int>& cp)
// {
// 	if(bf.find(cp)==bf.end())
// 		bf[cp]=tryCombination(cp.data());
// 	return bf[cp];
// }
bool ask(int l,int r)
{
	for(;l<=r;l++)
		if(!fix[l])
			cur[l]=!cur[l];
	int nc=tryCombination(cur.data());
	if(prv==d and (nc>d or nc==-1))
	{
		prv=nc;
		return 1;
	}
	else if((prv==-1 or prv>d) and nc==d)
	{
		prv=nc;
		return 1;
	}
	for(;l<=r;l++)
		if(!fix[l])
			cur[l]=!cur[l];
	prv=nc;
	return 0;
}
void find_switch(int l,int r)
{
	if(l==r)
	{
		fix[l]=1;
		sp[l]=d;
		if(prv==d)
		{
			cur[l]=!cur[l];
			prv=tryCombination(cur.data());
		}
		return;
	}
	int mid=(l+r)/2;
	if(ask(l,mid))
	{
		find_switch(l,mid);
	}
	else
	{
		find_switch(mid+1,r);
	}
}
void exploreCave(int n)
{
	cur.resize(n,0);
	sp.resize(n,0);
	fix.resize(n,0);
	prv=tryCombination(cur.data());
	for(d=0;d<n;d++)
		find_switch(0,n-1);
	answer(cur.data(),sp.data());
}

• Subtask 1: 12 / 12
• Subtask 2: 13 / 13
• Subtask 3: 21 / 21
• Subtask 4: 30 / 30
• Subtask 5: 24 / 24