Submission #593398

#	Time	Username	Problem	Language	Result	Execution time	Memory
593398		shezitt	Cave (IOI13_cave)	C++14	100 / 100	952 ms	460 KiB

cave

#include "cave.h"
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cassert>
#include <set>
 
using namespace std;
 
bool open(int q, int i){
	if(q == -1){
		return 1;
	}
	return q > i;
}
 
void exploreCave(int N) {
	int a[N], b[N];
	for(int i=0; i<N; ++i){
		a[i] = 0, b[i] = -1;
	}
	for(int i=0; i<N; ++i){
		bool p = 0;
		for(int j=0; j<N; ++j){
			if(b[j] == -1){
				a[j] = p;
			}
		}
		if(!open(tryCombination(a), i)){
			p = !p;
		}
		int l = 0, r = N-1, ans = -1;
		while(l < r){
			int mid = (l+r)/2;
			for(int j=0; j<N; ++j){
				if(b[j] == -1){
					if(j >= l && j <= mid){
						a[j] = p;
					} else {
						a[j] = !p;
					}
				}
			}
			if(open(tryCombination(a), i)){
				r = mid;
			} else {
				l = mid+1;
			}
		}
		b[r] = i;
		a[r] = p;
	}
	answer(a, b);
}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:32:23: warning: unused variable 'ans' [-Wunused-variable]
   32 |   int l = 0, r = N-1, ans = -1;
      |                       ^~~

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