제출 #467964

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
467964		SirCovidThe19th	동굴 (IOI13_cave)	C++17	100 / 100	1045 ms	560 KiB

cave

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

void exploreCave(int n){
    int door[n], move[n], use[n] = {}; 
    for (int i = 0; i < n; i++){
        int low = 0, high = n, A[n] = {}, openSt = 1;  
        memcpy(A, move, sizeof(move));
        auto setA = [&](int l, int r){
            for (int j = 0; j < n; j++) 
                if (!use[j])
                    A[j] = (j >= l and j <= r) ? openSt ^ 1 : openSt;
            return tryCombination(A) == i;
        };
		openSt = setA(0, n - 1); 
        while (low < high){
            int mid = (low + high) / 2;
            setA(low, mid) ? high = mid : low = mid + 1;
        }
        door[low] = i; move[low] = openSt; use[low] = 1;
    }
	answer(move, door);
}

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