Submission #360235

#	Time	Username	Problem	Language	Result	Execution time	Memory
360235		jesus_coconut	Cave (IOI13_cave)	C++17	100 / 100	1555 ms	768 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"

using namespace std;

int const MAXN = 5010;

void exploreCave(int N) {
    bitset<MAXN> bio;
    int S[N], D[N], Q[N];
    memset(S, 0, sizeof S);
    memset(D, 0, sizeof D);
    memset(Q, 0, sizeof Q);
    list<int> l;
    for (int i = 0; i < N; ++i) {
    	l.push_back(i);
    }
    for (int i = 0; i < N; ++i) {
    	int a = tryCombination(S);
    	int state = 0;
    	if (a != -1 && a == i) {
    		state = 1;
    	}
    	int lo = 0, hi = N - i;
    	while (lo < hi - 1) {
    		int mid = (lo + hi) / 2;
    		int cnt = 0;
    		for (int j = 0; j < N; ++j) {
    			if (bio[j]) Q[j] = S[j];
    		}
    		for (auto j : l) {
    			if (cnt >= lo && cnt < mid) Q[j] = state;
    			else Q[j] = !state;
    			++cnt;
    		}
    		a = tryCombination(Q);
    		if (a != -1 && a == i) {
    			lo = mid;
    		} else {
    			hi = mid;
    		}
    	}
    	auto it = l.begin();
    	advance(it, lo);
    	S[*it] = state;
    	D[*it] = i;
    	bio[*it] = true;
    	l.erase(it);
    }

    answer(S, D);
}

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