제출 #159617

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
159617		rama_pang	동굴 (IOI13_cave)	C++14	100 / 100	1217 ms	640 KiB

cave

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

void exploreCave(int N) {
    int guess[N] = {}, ans[N] = {}, order[N] = {}, fixed[N] = {};
    for (int i = 0; i < N; i++) ans[i] = -1, order[i] = -1, fixed[i] = 0;
    
    for (int i = 0; i < N; i++) {
        int le = 0, ri = N - 1;
        int sv = N - 1;

        for (int j = 0; j < N; j++) guess[j] = ans[j];
        for (int j = 0; j < N; j++) if (fixed[j] != 1) guess[j] = 1;

        int type = tryCombination(guess);
        if (type == -1) type = N;
        type = (type > i)? 1 : 0;

        while (le <= ri) {
            int mid = (le + ri) / 2;
            for (int j = 0; j < N; j++) {
                if (fixed[j] == 1) {
                    guess[j] = ans[j];
                } else if (j <= mid) {
                    guess[j] = type;
                } else {
                    guess[j] = type ^ 1;
                }
            }

            int check = tryCombination(guess);
            if (check == -1) check = N;

            if (check > i) {
                sv = mid;
                ri = mid - 1;
            } else {
                le = mid + 1;
            }
        }

        order[sv] = i;
        fixed[sv] = 1;
        ans[sv] = type;
    }

    answer(ans, order);
}

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