Submission #46346

#	Time	Username	Problem	Language	Result	Execution time	Memory
46346		Noam527	Cave (IOI13_cave)	C++17	100 / 100	1120 ms	640 KiB

cave

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <string>
#include <time.h>
#include <stack>
#include <queue>
#include <random>
#include <fstream>
#define endl '\n'
#define flush fflush(stdout), cout.flush()
#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define debug cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7, inf = 1e9 + 7;
const ll hs = 199;
const ldb eps = 1e-9, pi = acos(-1);
using namespace std;
 
#include "cave.h"
int tryCombination(int S[]);
void answer(int S[], int D[]);
void exploreCave(int N);
 
struct tag {
	int to, correct;
	tag(int ii = 0) {
		to = ii;
		correct = 0;
	}
};
 
int n, send[5000], solved;
vector<tag> a;
 
int check(int first) {
	for (int i = 0; i < n; i++)
		if (i <= first)
			send[a[i].to] = a[i].correct;
		else
			send[a[i].to] = 1 ^ a[i].correct;
	
	return tryCombination(send);
}
 
void findnext() {
	static int lo, hi, mid, nval;
	lo = solved;
	hi = n - 1;
	if (check(solved - 1) == solved) {
		nval = 0;
		// find first point where check(k) != solved
		while (lo < hi) {
			mid = (lo + hi) / 2;
			if (check(mid) == solved) lo = mid + 1;
			else hi = mid;
		}
	}
	else {
		nval = 1;
		// find first point where check(k) == solved
		while (lo < hi) {
			mid = (lo + hi) / 2;
			if (check(mid) != solved) lo = mid + 1;
			else hi = mid;
		}
	}
	swap(a[lo], a[solved]);
	a[solved].correct = nval;
}
 
void exploreCave(int N) {
	n = N;
 
	a.resize(n);
	for (int i = 0; i < n; i++) a[i] = tag(i);
	for (solved = 0; solved < n; solved++)
		findnext();
 
	int S[5000], D[5000];
	for (int i = 0; i < n; i++) S[a[i].to] = a[i].correct;
	for (int i = 0; i < n; i++) D[a[i].to] = i;
 
	answer(S, D);
}

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