Submission #1357700

#	Time	Username	Problem	Language	Result	Execution time	Memory
1357700		ezzzay	Cave (IOI13_cave)	C++20	100 / 100	83 ms	564 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
void exploreCave(int N) {
    vector<int>col(N);   
    vector<int>con(N);   
    vector<int>vc;         
    for(int i=0;i<N; i++)vc.pb(i);

    for (int i=0;i<N;i++) {
        int b=tryCombination(col.data());
        bool u=(b==i);
        int s=0;
        for (int j=12;j>=0;j--) {
            if (s+(1<<j)<=(int)vc.size()) {
                for(int k=s; k<s+(1<<j);k++) {
                    col[vc[k]]^=1;
                }
                int c = tryCombination(col.data());
                for (int k = s; k < s + (1 << j); k++) {
                    col[vc[k]] ^= 1;
                }
                bool p=(c==i);
                if(p==u)s+=(1<<j);
            }
        }
        con[vc[s]] = i;
        col[vc[s]] = u;
        vc.erase(vc.begin() + s);
    }
    answer(col.data(), con.data());
}

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