Submission #1310716

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310716		putuputu	Cave (IOI13_cave)	C++20	100 / 100	382 ms	536 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
void exploreCave(int n) {
    vector<int> state(n, 0);      
    vector<int> dswitch(n, 0);    
    vector<int> use(n, 0);        
    for (int h=0; h<n; h++){
        for (int i=0; i<n; i++){
            if (!use[i]){
                state[i]=0;
            } 
        } 
        int a=tryCombination(state.data());
        int ka=(a!=h) ? 0 : 1;
        for (int i=0; i<n; i++){
            if (!use[i]){
                state[i]=1-ka;
            } 
        } 
        int l=0, r=n-1;
        int ans=-1;
        while (l<=r){
            int mid=(l+r)/2;
            for (int i=l; i<=mid; i++){
                if (!use[i]){
                    state[i]=ka;
                } 
            } 
            int a2=tryCombination(state.data());
            if (a2!=h){
                r=mid-1;
                ans=mid;
            }else{
                l=mid+1;
            }
            for (int i=l; i<=mid; i++){
                if (!use[i]){
                    state[i]=1-ka;
                } 
            } 
        }
        if (ans==-1){
            ans=l-1;
        } 
        dswitch[ans]=h; 
        state[ans]=ka;
        use[ans]=1;    
    }
    answer(state.data(), dswitch.data());
}

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