Submission #197489

#	Time	Username	Problem	Language	Result	Execution time	Memory
197489		handlename	Cave (IOI13_cave)	C++17	100 / 100	1349 ms	640 KiB

cave

#include <bits/stdc++.h>
#include"cave.h"
using namespace std;
void exploreCave(int n) {
    int fixed[n];
    memset(fixed,-1,sizeof(fixed));
    int posi[n];
    for (int i=0;i<n;i++){
        int s[n];
        memset(s,0,sizeof(s));
        for (int j=0;j<n;j++){
            if (fixed[j]!=-1) s[j]=fixed[j];
        }
        int ori=0;
        if (tryCombination(s)!=i) ori=1;
        int mini=0,maxi=n;
        while (mini+1<maxi){
            int middle=(mini+maxi)/2;
            for (int j=0;j<n;j++){
                s[j]=ori;
            }
            for (int j=mini;j<middle;j++){
                s[j]=1-ori;
            }
            for (int j=0;j<n;j++){
                if (fixed[j]!=-1){
                    s[j]=fixed[j];
                }
            }
            if (tryCombination(s)!=i){
                maxi=middle;
            }
            else {
                mini=middle;
            }
        }
        posi[mini]=i;
        fixed[mini]=1-ori;
    }
    answer(fixed,posi);
}

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