제출 #991091

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
991091		Muhammet	동굴 (IOI13_cave)	C++17	100 / 100	468 ms	600 KiB

cave

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

using namespace std;

void exploreCave(int n) {
    int s[n], a[n], b[n], vis[n];
    for(int i = 0; i < n; i++) vis[i] = a[i] = b[i] = 0;
    for(int i = 0; i < n; i++){
        int l = 0, r = n-1, k = 0;
        int x = tryCombination(a);
        while(l <= r){
            int md = (l + r) / 2;
            for(int j = 0; j < n; j++){
                if(vis[j] == 0){
                    if(j >= l and j <= md) s[j] = 1;
                    else s[j] = 0;
                }
                else {
                    s[j] = a[j];
                }
            }
            int y = tryCombination(s);
            bool tr = 0;
            if(x == i){
                if(y != i){
                    tr = 1;
                }
            }
            else {
                if(y == i){
                    tr = 1;
                }
            }
            if(tr == 1){
                r = md-1;
                k = md;
            }
            else {
                l = md+1;
            }
        }
        vis[k] = 1;
        a[k] = (x == i);
        b[k] = i;
    }

    answer(a, b);

    return;
}

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