Submission #384092

#	Time	Username	Problem	Language	Result	Execution time	Memory
384092		alishahali1382	Cave (IOI13_cave)	C++14	100 / 100	486 ms	748 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXN=5010;

int A[MAXN];
int match[MAXN], mark[MAXN];

inline int ask(){ return tryCombination(A);}

void exploreCave(int n){
	for (int i=0; i<n; i++) mark[i]=1;
	for (int i=0; i<n; i++){
		if (ask()!=i) for (int j=0; j<n; j++) A[j]^=mark[j];
		// now tryCombination is i
		int dwn=0, up=n;
		while (up-dwn>1){
			int mid=(dwn+up)>>1;
			for (int j=0; j<mid; j++) A[j]^=mark[j];
			if (ask()==i) dwn=mid;
			else up=mid;
			for (int j=0; j<mid; j++) A[j]^=mark[j];
		}
		match[dwn]=i;
		mark[dwn]=0;
		A[dwn]^=1;
	}
	answer(A, match);
}

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