Submission #236054

#	Time	Username	Problem	Language	Result	Execution time	Memory
236054		socho	Cave (IOI13_cave)	C++14	100 / 100	321 ms	636 KiB

cave

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

void exploreCave(int N) {
	
	int correct_switch[N]; // i -> does switch i need on (1) ? or off (0) ?
	int switch_for_door[N]; // i -> what door does switch i connect to?
	int door_for_switch[N]; // i -> what switch does door i connect to?
	
	bool locked[N]; // i -> is switch i locked, and unchangeable?
	memset(locked, 0, sizeof locked);
	
	for (int i=0; i<N; i++) {
		
		// let's try to get past door #i
		
		// first, what is the correct state for door i?
		int co[N];
		for (int i=0; i<N; i++) {
			if (locked[i]) co[i] = correct_switch[i];
			else co[i] = 1;
		}
		// guaranteed to go i, or > i
		int which = tryCombination(co);
		
		int correct_for_door = 0;
		if (which == -1 || which > i) {
			// it means, 1 is correct for this door, whatever switch it is
			correct_for_door = 1;
		}
		
		// now, we must try to find, using binary search, where is the right switch for this door?
		
		int low = 0;
		int high = N-1;
		
		while (low < high) {
			// it can be any switch from low..high,
			int mid = (low + high) / 2;
			// cout << low << ' ' << mid << ' ' << high << endl;
			// set all from low..mid to correct, and mid+1..high to wrong
			// if we can still go through, switch must be on left
			// otherwise, switch must be on the right
			for (int X=low; X<=mid; X++) {
				if (locked[X]) co[X] = correct_switch[X];
				else co[X] = correct_for_door;
			}
			for (int X=mid+1; X<=high; X++) {
				if (locked[X]) co[X] = correct_switch[X];
				else co[X] = 1 - correct_for_door;
			}
			int result = tryCombination(co);
			if (result == -1 || result > i) {
				// the door is open, it must be on the left side
				high = mid;
			}
			else {
				// the door is closed, it must be on the right side
				low = mid+1;
			}
		}
		
		// now, low and high should be equal, and this is the position of the right switch
		// cout << "door: " << i << ", switch: " << low << endl;
		switch_for_door[i] = low;
		door_for_switch[low] = i;
		locked[low] = true;
		correct_switch[low] = correct_for_door;
		
	}
	
	answer(correct_switch, door_for_switch);
	
}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:8:6: warning: variable 'switch_for_door' set but not used [-Wunused-but-set-variable]
  int switch_for_door[N]; // i -> what door does switch i connect to?
      ^~~~~~~~~~~~~~~

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