Submission #630611

#	Time	Username	Problem	Language	Result	Execution time	Memory
630611		ttamx	Cave (IOI13_cave)	C++17	100 / 100	923 ms	476 KiB

cave

#include "cave.h"
#include<bits/stdc++.h>

using namespace std;

void exploreCave(int n) {
    int s[n],d[n];
    bool vis[n];
    for(int i=0;i<n;++i)s[i]=d[i]=vis[i]=0;
    for(int i=0;i<n;++i){
        int st;
        if(tryCombination(s)==i)st=1;
        else st=0;
        int l=0,r=n-1;
        while(l<r){
            int m=(l+r)/2;
            int tmp[n];
            for(int j=0;j<n;++j)if(!vis[j])tmp[j]=st;else tmp[j]=s[j];
            for(int j=l;j<=m;++j)if(!vis[j])tmp[j]=1-st;
            if(tryCombination(tmp)==i)r=m;
            else l=m+1;
        }
        s[r]=st;
        vis[r]=1;
        d[r]=i;
    }
    answer(s,d);
}

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