Submission #584728

#	Time	Username	Problem	Language	Result	Execution time	Memory
584728		kkkkkkkk	Cave (IOI13_cave)	C++14	100 / 100	1303 ms	672 KiB

cave

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

const int MAXN = 5010;

int isDefined[MAXN],definedState[MAXN],whichNumber[MAXN],N;
int queryArray[MAXN];

int opens_kth(int got_ans,int target) //vrakja dali kje ja otvori vratata switchot
{
	if (got_ans == -1) //ako svite vrate sa otvoreni
	    return 1;
	return got_ans>target; //kje vrati 1 ako e otvorena vratata
}

void divide_and_conquer(int target,int left,int right,int known_color)
{
	if (left == right) //base case, ova e baraniot switch
	{
		isDefined[left] = 1;
		definedState[left] = known_color;
		whichNumber[left] = target;
		return;
	}

	memset(queryArray,0,sizeof(queryArray));
	int mid = (left + right)/2;
	for (int i = 0;i<N;i++) //u prvata polovina gi stava known_color, a u vtorata drugata boja
	{
		if (left <= i && i <= mid)
			queryArray[i] = known_color;
		else
			queryArray[i] = 1 ^ known_color;
	}
	for (int i = 0;i<N;i++) //gi stavamo tija sto vise gi znaemo
		if (isDefined[i]) 
		    queryArray[i]=definedState[i];

	int ans=tryCombination(queryArray);
	if (opens_kth(ans,target)) //ako ja otvara so plava
		divide_and_conquer(target,left,mid,known_color);
	else
		divide_and_conquer(target,mid+1,right,known_color);
}

int which_color(int target)
{
	memset(queryArray,0,sizeof(queryArray));
	for (int i = 0;i<N;i++) //dali ja imamo najdeno vrednosta
		if (isDefined[i]) 
		    queryArray[i] = definedState[i];
	
	int ans = tryCombination(queryArray); //sve sa plavi osven najdenite
	if (opens_kth(ans,target)) 
	    return 0;
	else 
	    return 1;
}

void exploreCave(int n) 
{
    N=n;
    for (int i=0;i<N;i++)
    {
    	int known_color = which_color(i);
    	divide_and_conquer(i,0,N-1,known_color);
    }

    answer(definedState,whichNumber);

}

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