Submission #383954

#	Time	Username	Problem	Language	Result	Execution time	Memory
383954		alireza_kaviani	Cave (IOI13_cave)	C++11	100 / 100	350 ms	876 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"
using namespace std;

const int MAXN = (1 << 13) - 1;
const int LOG = 13;

int res[MAXN] , val[MAXN] , s[LOG][MAXN] , valid[MAXN];

void exploreCave(int N) {
	for(int i = 0 ; i < LOG ; i++){
		for(int j = 0 ; j < N ; j++){
			if(j & (1 << i))	s[i][j] = 1;
		}
	}
	for(int i = 0 ; i < N ; i++){
		int ans = 0;
		for(int j = 0 ; j < LOG ; j++){
			int cur = tryCombination(s[j]);
			if(cur > i || cur == -1)	ans |= (1 << j);
		}
		int cur = tryCombination(valid);
//		cout << i << ' ' << cur << ' ' << ans << ' ';
		if(cur > i || cur == -1){
			ans ^= MAXN;
			res[ans] = i;
			val[i] = 0;
			for(int j = 0 ; j < LOG ; j++)	s[j][ans] = 0;
		}
		else{
			res[ans] = i;
			val[i] = 1;
			valid[ans] = 1;
			for(int j = 0 ; j < LOG ; j++)	s[j][ans] = 1;
		}
//		cout << ans << endl;
	}
	answer(valid , res);
	return;
}

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