Submission #161622

#	Time	Username	Problem	Language	Result	Execution time	Memory
161622		kostia244	Cave (IOI13_cave)	C++14	100 / 100	705 ms	604 KiB

cave

#include "cave.h"
#include<bits/stdc++.h>
const int maxn = 5051;
int n;
int S[maxn], D[maxn];
void fill(int v, int q) {
	int c = 0;
	for(int i = 0;i < n&&c<q; i++) {
		if(D[i]==-1)c++,S[i]=v;
	}
}
int get(int x) {
	int i = 0, c = 0;
	while(c < x) {
		if(D[i]==-1)c++;
		if(c!=x)i++;
	}
	return i;
}
void exploreCave(int N) {
	n = N;
	memset(S, 0, sizeof S);
	memset(D, -1, sizeof D);
	int c = 0;
	int x = 0;
	for(int i = 0; i < n; i++) {
		fill(1, n);
		x = tryCombination(S);
		if(x>i||x==-1) {
			x=1;
		} else {
			x=0;
		}
		fill(x^1, n);
		int a = 0, ps = 0, c = 0;
		for(int j = 1<<12; j; j>>=1) {
			if(a+j>(n-i))continue;
			while(c < (a+j)) {
				if(D[ps]==-1)S[ps]=x, c++;
				ps++;
			}
			while(c > (a+j)) {
				ps--;
				if(D[ps]==-1)S[ps]=x^1, c--;
			}
			int t = tryCombination(S);
			if(t<=i&&t!=-1) {
				a+=j;
			}
//			cout << a << " : ";for(int i = 0; i < n; i++) cout << S[i]
		}
		a = get(a+1);
		D[a] = i;
		S[a] = x;
	}
	answer(S, D);
}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:24:6: warning: unused variable 'c' [-Wunused-variable]
  int c = 0;
      ^

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