Submission #388620

#	Time	Username	Problem	Language	Result	Execution time	Memory
388620		Antekb	Cave (IOI13_cave)	C++14	100 / 100	249 ms	844 KiB

cave

#include "cave.h"
//#include<iostream>
void exploreCave(int n){
	int k=14;
	while((1<<k)>=n)k--;
	k++;
	int w[k+1][n];
	for(int j=0; j<k; j++){
		for(int i=0; i<n; i++)w[j][i]=!!((1<<j)&i);
	}
	for(int i=0; i<n; i++)w[k][i]=1;
	int pos[n];
	for(int i=0; i<n; i++){
		int id=0;
		for(int j=0; j<k; j++){
			int l=tryCombination(w[j]);
			//std::cerr<<l;
			if(l==-1)l=n;
			if(l>i)id+=(1<<j);
		}
		int l=tryCombination(w[k]);
		if(l==-1)l=n;
		bool b=1;
		if(l<=i){
			id=((1<<k)-1)^id;
			b=0;
		}
		pos[id]=i;
		for(int j=0; j<=k; j++)w[j][id]=b;
	}
	answer(w[0], pos);
}

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