Submission #739165

#	Time	Username	Problem	Language	Result	Execution time	Memory
739165		josanneo22	Cave (IOI13_cave)	C++17	100 / 100	164 ms	468 KiB

cave

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

#define pb push_back
#define mp make_pair
#define fi first
#define se second
 
#include "cave.h"
void exploreCave(int N) {
    int n;
    n = N;
    int comb[n], door[n];
    for (int i = 0; i < n; i++)
        comb[i] = 0, door[i] = -1;
 
    int now, ret;
    for (int i = 0; i < n; i++) {
        int l = 0, r = n-1;
        now = (tryCombination(comb) == i ? 1 : 0);
        while (l < r) { 
            int mid = (l + r) / 2;
            for (int j = l; j <= mid; j++) {
                if (door[j] != -1) continue;
                comb[j] = 1-comb[j];
            } 
            ret = tryCombination(comb);
            if ((ret == i && !now) || (ret != i && now)) {
                r = mid, now = 1-now;
            } else {
                l = mid+1;
            }
        }
        door[l] = i; 
        if (now) comb[l] = 1-comb[l];
    } 
    answer(comb, door);
}
/*
void solve(){

}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
    int tt; cin>>tt;
	while(tt--) solve();
}
*/

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