Submission #375658

#	Time	Username	Problem	Language	Result	Execution time	Memory
375658		vot808	Cave (IOI13_cave)	C++17	100 / 100	994 ms	640 KiB

cave

#include "bits/stdc++.h"
#include "cave.h"
//#include "grader.c"
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef array<int, 2> ii;
// #define endl '\n'

void exploreCave(int n) {
	vi curr(n), initIdx(n), ansIdx(n, -1);
	int qr[n] = {0};
	int last = tryCombination(qr);
	
	for_(i, 0, n) initIdx[i] = i;
	
	for_(i, 0, n) {
		int pt = 0;
		if (last == -1 or last > i) {
			for_(j, 0, curr.size()) curr[j] = 1-curr[j];
			for_(j, 0, n) if (ansIdx[j] == -1) qr[j] = curr[pt++];
		}
		
		// cout << "starting " << i << " with assuming that it is closed when in query: ";
		// for_(j, 0, n) cout << qr[j];
		// cout << endl;
		
		int l = 0, r = curr.size(), ans = -1;
		while (l < r) {
			int mid = (l+r)/2;
			pt = 0;
			for_(j, 0, n) if (ansIdx[j] == -1) {
				if (pt <= mid) qr[j] = 1-curr[pt];
				else qr[j] = curr[pt];
				pt++;
			}
			
			if ((last = tryCombination(qr)) > i or last == -1) {
				r = ans = mid;
			} else l = mid+1;
			
			// cout << "for mid " << mid << ": ";
			// for_(j, 0, n) cout << qr[j];
			// cout << " value: " << last << endl;
		}
		
		// cout << "got ans " << ans << " " << initIdx[ans] << endl;
		qr[initIdx[ans]] = 1-curr[ans];
		pt = 0;
		for_(j, 0, n) if (ansIdx[j] == -1) {
			curr[pt] = qr[j];
			pt++;
		}
		last = tryCombination(qr);
		
		// cout << "ending with qr: ";
		// for_(j, 0, n) cout << qr[j];
		// cout << " and value " << last << endl;
		
		ansIdx[initIdx[ans]] = i;
		curr.erase(curr.begin()+ans);
		initIdx.erase(initIdx.begin()+ans);
	}
	
	// cout << "got final indices: " << endl;
	// for (auto i: ansIdx) cout << i << " ";
	// cout << endl;
	
	int finIdx[n], finState[n];
	for_(i, 0, n) {
		finIdx[i] = ansIdx[i];
	}
	
	answer(qr, finIdx);
}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:71:17: warning: unused variable 'finState' [-Wunused-variable]
   71 |  int finIdx[n], finState[n];
      |                 ^~~~~~~~

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