Submission #221814

#	Time	Username	Problem	Language	Result	Execution time	Memory
221814		patrikpavic2	Cave (IOI13_cave)	C++17	100 / 100	1170 ms	640 KiB

cave

/**
* user:  ppavic
* fname: Patrik
* lname: Pavić
* task:  cave
* score: 100.0
* date:  2019-07-03 13:57:02.364346
*/
#include "cave.h"
#include <cstdio>
#include <cstdlib>

using namespace std;

const int N = 5000;

int cur[N], bio[N], ans[N], n, P[N];

int guess(int x){
	for(int i = 0;i <= x;i++)
		if(!bio[i]) cur[i] = !cur[i];
	int ret = tryCombination(cur);
	for(int i = 0;i <= x;i++)
		if(!bio[i]) cur[i] = !cur[i];
	return ret;
}

void namjesti(int x){
	for(int i = 0;i < n;i++){
		if(bio[i]) cur[i] = ans[i];
		else cur[i] = rand() % 2;
	}
	int xx = tryCombination(cur);
	if(x == xx) return;
	for(int i = 0;i < n;i++)
		if(!bio[i]) cur[i] = !cur[i];
}

void exploreCave(int nn) {
    n = nn;
    for(int i = 0;i < n;i++){
    	namjesti(i);
    	int c_ans = -1;
    	for(int j = 15;j >= 0;j--){
    		if(c_ans + (1 << j) >= n - 1) continue;
    		c_ans += (1 << j);
    		if(guess(c_ans) != i)
    			c_ans -= (1 << j);
    	}
    	c_ans++;
    	//printf("c_ans = %d\n", c_ans);
    	ans[c_ans] = !cur[c_ans];
    	bio[c_ans] = 1;
    	P[c_ans] = i;
    }
    answer(ans, P);
}

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