Submission #3008

#	Time	Username	Problem	Language	Result	Execution time	Memory
3008		cki86201	동굴 (IOI13_cave)	C++98	100 / 100	348 ms	544 KiB

cave

#include "cave.h"

int D[5050],S[8200];
int u;
bool check[5050];

int solve(int s,int d,int h,bool now)
{
	if(h==-1){
		now?0:S[s]^=1;
		return s;
	}
	int i;
	for(i=(s+d)>>1;i<d;i++){
		if(!check[i])S[i]^=1;
	}
	bool p=(tryCombination(S)!=u);
	if(now^p)return solve((s+d)>>1,d,h-1,p);
	else return solve(s,(s+d)>>1,h-1,p);
}

void exploreCave(int N) {
    int i,j,k;
    for(i=0;i<N;i++){
		u=i;
		int t=solve(0,(1<<13),12,tryCombination(S)!=i);
		D[t]=i;
		check[t]=1;
    }
    answer(S,D);
}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:23:11: warning: unused variable 'j' [-Wunused-variable]
     int i,j,k;
           ^
cave.cpp:23:13: warning: unused variable 'k' [-Wunused-variable]
     int i,j,k;
             ^

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