Submission #578859

#	Time	Username	Problem	Language	Result	Execution time	Memory
578859		enerelt14	Cave (IOI13_cave)	C++14	100 / 100	648 ms	468 KiB

cave

#include "cave.h"
#include<bits/stdc++.h>
using namespace std;
void exploreCave(int N) {
    int n=N, s[N], d[N], re[N], ans[N];
    for (int i=0;i<N;i++){
        bool is=0;
        for (int j=0;j<n;j++)s[j]=0;
        for (int j=0;j<i;j++)s[re[j]]=ans[re[j]];
        if (tryCombination(s)==i)is=1;
        else is=0;
        int l=0, r=N-1;
        while(l!=r){
            int mid=(l+r)/2;
            for (int j=l;j<=mid;j++)s[j]=1-s[j];
            for (int j=0;j<i;j++)s[re[j]]=ans[re[j]];
            if (tryCombination(s)==i){
                if (is)l=mid+1;
                else{
                    is=1;
                    r=mid;
                }
            }
            else{
                if (is){
                    is=0;
                    r=mid;
                }
                else l=mid+1;
            }
        }
        d[l]=i;
        re[i]=l;
        if (is){
            ans[l]=1-s[l];
        }
        else{
            ans[l]=s[l];
        }
    }
    answer(ans, d);
}

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