Submission #812747

#	Time	Username	Problem	Language	Result	Execution time	Memory
812747		Kerim	Cave (IOI13_cave)	C++17	100 / 100	1000 ms	448 KiB

cave

#include "cave.h"
#include "bits/stdc++.h"
using namespace std;
void exploreCave(int n) {
	vector<int>a(n),b(n);
	for(int i=0;i<n;i++)a[i]=-1;
	for(int i=0;i<n;i++){
      	vector<int> c(n, 0);
		for(int j=0;j<n;j++)
			if(~a[j])
              	c[j]=a[j];
		int val=(tryCombination(c.data())==i);
		int st=0,en=n-1;
		while(st<en){
			int mid=(st+en+1)>>1;
			for(int j=0;j<n;j++)
				if(a[j] == -1)
                  	c[j]=val^(j<mid);	
			if(tryCombination(c.data())==i) 
              	en=mid-1;
			else 
              	st=mid;
		}
      	a[st]=val;
      	b[st]=i;
	}
	answer(a.data(),b.data());
}

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