Submission #131959

#	Time	Username	Problem	Language	Result	Execution time	Memory
131959		junodeveloper	Cave (IOI13_cave)	C++14	21 / 100	83 ms	516 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
int S[5010], D[5010], rev[5010];
int Try() {
	return tryCombination(S);
}
void exploreCave(int N) {
	memset(D, -1, sizeof(D));
	srand(123);
	for(int i=0; i<N; i++) S[i] = rand() % 2;
	int s = 0, x, B, idx, nxt = Try(), tmp;
	while(1) {
		idx = nxt;
		if(idx != -1) x = idx - s + 1;
		else x = N - s;
		B = sqrt((N - s) / x);
		vector<int> a;
		int f = -1;
		for(int i=0; i<N; i++) {
			if(D[i] == -1) {
				a.push_back(i);
				if(a.size() == B) {
					for(auto& j : a) S[j] ^= 1;
					tmp = Try();
					if(idx != tmp) {
						for(auto& j : a) S[j] ^= 1;
						for(auto& j : a) {
							S[j] ^= 1;
							int t = Try();
							if((t != -1 && t < idx) || idx == -1) {
								while(t == -1);
								rev[t] = j;
								D[j] = t;
							} else if(t == -1 || idx < t) {
								rev[idx] = j;
								D[j] = idx;
								f = j;
								nxt = t;
							}
							S[j] ^= 1;
						}
						for(auto& j : a) S[j] ^= 1;
					}
					for(auto& j : a) S[j] ^= 1;
					a.clear();
				}
			}
		}
		if(a.size() > 0) {
			for(auto& j : a) S[j] ^= 1;
			tmp = Try();
			if(idx != tmp) {
				for(auto& j : a) S[j] ^= 1;
				for(auto& j : a) {
					S[j] ^= 1;
					int t = Try();
					if((t != -1 && t < idx) || idx == -1) {
						while(t == -1);
						rev[t] = j;
						D[j] = t;
					} else if(t == -1 || idx < t) {
						rev[idx] = j;
						D[j] = idx;
						f = j;
						nxt = t;
					}
					S[j] ^= 1;
				}
				for(auto& j : a) S[j] ^= 1;
			}
			for(auto& j : a) S[j] ^= 1;
			a.clear();
		}
		if(f != -1) S[f] ^= 1;
		if(idx == -1) break;
		s = idx + 1;
	}
	answer(S, D);
}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:23:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(a.size() == B) {
        ~~~~~~~~~^~~~

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