Submission #196896

#	Time	Username	Problem	Language	Result	Execution time	Memory
196896		Juney	Cave (IOI13_cave)	C++14	100 / 100	867 ms	640 KiB

cave

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

const int MAXN = 5e3 + 5;

int chk(int arr[]) { return tryCombination(arr); }

int done, dc[MAXN], door[MAXN], ans[MAXN], sw[MAXN];
int one[MAXN], A[MAXN];

void f(int l, int r, int col) {
	if(l == r) {
		done++;
		dc[done] = 1-col;
		door[done] = l;
		return;
	}
	int mid = l + r >> 1;
	for(int i=0; i<l; i++) A[i] = 1-col;
	for(int i=l; i<=mid; i++) A[i] = col;
	for(int i=mid+1; i<=r; i++) A[i] = 1-col;
	for(int i=0; i<=done; i++) A[door[i]] = dc[i];
	if(chk(A) == done+1) f(l, mid, col);
	else f(mid+1, r, col);
} 

void exploreCave(int N) {
	done = -1;
    for(int i=0; i<N; i++) one[i] = 1;
    for(int i=0; i<N; i++) {
		for(int j=0; j<=done; j++) one[door[j]] = dc[j];
		if(chk(one) == done+1) f(0, N-1, 1);
		else f(0, N-1, 0);
    }
	for(int i=0; i<N; i++) ans[door[i]] = i;
	for(int i=0; i<N; i++) sw[door[i]] = dc[i];
	answer(sw, ans);
}

Compilation message (stderr)

cave.cpp: In function 'void f(int, int, int)':
cave.cpp:19:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~

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