Submission #919030

#	Time	Username	Problem	Language	Result	Execution time	Memory
919030		harrisyu9696	동굴 (IOI13_cave)	C++14	100 / 100	236 ms	696 KiB

cave

#include<bits/stdc++.h>
#include "cave.h"
using namespace std;

void exploreCave(int N){
    int n=N;
    int cur[n]={}, d[n]={};
    bool done[n]={};
    for(int i=0; i<n; i++){
        int tmp=tryCombination(cur);
        int con=(tmp==-1||tmp>i);

        int l=0, r=n-1;
        while(l!=r){
            int mid=(l+r)/2;
            for(int j=l; j<=mid; j++){
                if(!done[j]) cur[j]^=1;
            }
            int len=tryCombination(cur);
            int now=(len==-1||len>i);
            for(int j=l; j<=mid; j++){
                if(!done[j]) cur[j]^=1;
            }   
            if(now!=con) r=mid; // 把前半改掉會變成不同情況 -> 控制門 i 的開關在前半
            else l=mid+1;
        }
        done[l]=1;
        d[l]=i;
        cur[l]=1-con;
    }
    answer(cur, d);
}

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