Submission #283504

#	Time	Username	Problem	Language	Result	Execution time	Memory
283504		Shush	Cave (IOI13_cave)	C++17	100 / 100	286 ms	512 KiB

cave

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

using namespace std;

int n, *s, *t, last;

void flip(int start, int end){
	for(int i = start; i <= end; i++){
		if(t[i] != -1) continue;
		s[i] = 1 - s[i];
	}
}

int bs(int j){
	int lo = 0, hi = n - 1, mid, res = -1;
	while(lo <= hi){
		mid = (lo + hi)/2;
		flip(mid, hi);
		int next = tryCombination(s);
//		cerr << mid << " " << hi << '\n';
//		for(int i = 0; i < n; i++){
//			cerr << s[i] << ' ';
//		}
//		cerr << '\n';
//		cerr << " " << last << " " <<  next << '\n';
		if(next != last && (next == j || last == j)){
			lo = mid + 1;
			res = mid;
		}
		else {
			hi = mid - 1;
		}
		last = next;
	}
	return res;
}

void exploreCave(int N) {
	n = N;
	s = new int[n];
	t = new int[n];
	//Initializing
	for(int i = 0; i < n; i++){
		t[i] = -1;
		s[i] = 0;
	}
	int j = 0;
	while(j < n){
		last = tryCombination(s);
		int i = bs(j);
		t[i] = j;
		if(last == j) s[i] = 1 - s[i]; 
		j++;
	}
	answer(s, t);
}

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