Submission #17212

#	Time	Username	Problem	Language	Result	Execution time	Memory
17212		erdemkiraz	Cave (IOI13_cave)	C++98	100 / 100	1369 ms	632 KiB

cave

#include <bits/stdc++.h>

using namespace std;

#define type(x) __typeof((x).begin())
#define foreach(it, x) for(type(x) it = (x).begin(); it != (x).end(); it++)
typedef long long ll;
typedef pair < int, int > ii;

const int inf = 1e9 + 333;
const ll linf = 1e18 + inf;

#include "cave.h"

const int N = 5000 + 5;

int n;
int a[N], q[N], ans[N];

int f(int x, int k) {
	for(int i = 0; i < n; i++) {
		if(a[i] != -1)
			q[i] = a[i];
		else if(i <= x)
			q[i] = k;
		else
			q[i] = !k;
	}
	return tryCombination(q);
}

void exploreCave(int n) {
	:: n = n;
	memset(a, -1, sizeof(a));
	for(int i = 0; i < n; i++) {
		if(f(n - 1, 0) != i) {
			//open -> 0
			int l = 0, r = n - 1;
			while(l < r) {
				int m = l + r >> 1;
				if(f(m, 0) == i)
					l = m + 1;
				else
					r = m;
			}
			ans[l] = i;
			a[l] = 0;
			//printf("i = %d l = %d\n", i, l);
		}
		else {
			//open -> 1
			int l = 0, r = n - 1;
			while(l < r) {
				int m = l + r >> 1;
				if(f(m, 1) == i)
					l = m + 1;
				else
					r = m;
			}
			ans[l] = i;
			a[l] = 1;
			//printf("i = %d l = %d\n", i, l);
		}
	}
	answer(a, ans);
}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:40:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m = l + r >> 1;
             ~~^~~
cave.cpp:54:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m = l + r >> 1;
             ~~^~~

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