Submission #1199698

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199698		Hamed_Ghaffari	Cave (IOI13_cave)	C++20	100 / 100	206 ms	592 KiB

cave

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

const int MXN = 5003;

int S[MXN], ans[MXN];

void exploreCave(int n) {
    vector<int> vec(n);
    iota(vec.begin(), vec.end(), 0);
    for(int i=0; i<n; i++) {
        bool cl = tryCombination(S)==i;
        int l=0, r=vec.size(), mid;
        while(r-l>1) {
            mid = l+r>>1;
            for(int i=0; i<mid; i++)
                S[vec[i]] = 1;
            if((tryCombination(S)==i)!=cl)
                r=mid;
            else
                l=mid;
            for(int i=0; i<mid; i++)
                S[vec[i]] = 0;
        }
        ans[vec[l]] = i;
        if(cl) S[vec[l]] ^= 1;
        vector<int> nw;
        for(int i=0; i<vec.size(); i++)
            if(i!=l)
                nw.push_back(vec[i]);
        vec = nw;
    }
    answer(S, ans);
}

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