Submission #421293

#	Time	Username	Problem	Language	Result	Execution time	Memory
421293		jlallas384	Cave (IOI13_cave)	C++17	100 / 100	1134 ms	808 KiB

cave

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

int *inp,*ans;
int chk(vector<int> a){
    for(int x: a){
        inp[x] ^= 1;
    }
    int res = tryCombination(inp);
    for(int x: a){
        inp[x] ^= 1;
    }
    return res;   
}

void exploreCave(int n){
    inp = new int[n];
    ans = new int[n];
    set<int> st;
    for(int i = 0; i < n; i++){
        inp[i] = 0;
        st.insert(i);
    }
    for(int i = 0; i < n; i++){
        if(chk({i}) == 0){
            inp[i] ^= 1;
            break;
        }
    }
    int cur = 0;
    while(1){
        vector<int> b(st.begin(), st.end());
        int lst = -1,lo = 0,hi = b.size() - 1;
        while(lo <= hi){
            int m = (lo + hi) / 2;
            int res = chk(vector<int>(b.begin(),b.begin() + m + 1));
            if(res > cur || res == -1){
                hi = m - 1;
                lst = m;
            }else{
                lo = m + 1;
            }
        }
        assert(lst != -1);
        int nxt = chk({b[lst]});
        inp[b[lst]] ^= 1;
        st.erase(b[lst]);
        if(nxt == -1) break;
        for(int i = 1; i <= nxt - cur - 1; i++){
            vector<int> b(st.begin(), st.end());
            lst = -1,lo = 0,hi = b.size() - 1;
            while(lo <= hi){
                int m = (lo + hi) / 2;
                if(chk(vector<int>(b.begin(),b.begin() + m + 1)) == cur + i){
                    hi = m - 1;
                    lst = m;
                }else{
                    lo = m + 1;
                }
            }
            assert(lst != -1);
            st.erase(b[lst]);
        }
        cur = nxt;
    }
    for(int i = 0; i < n; i++){
        ans[i] = chk({i});
    }
    answer(inp,ans);
}

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