제출 #256362

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
256362		A02	동굴 (IOI13_cave)	C++14	100 / 100	551 ms	636 KiB

cave

#include "cave.h"
#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <set>

using namespace std;


void exploreCave(int N) {

    vector<int> solved_position (N, -1); //correct position for switch i.
    vector<int> solved_door (N, -1); //door switch i is connected to.

    for (int current_door = 0; current_door < N; current_door++){

        vector<int> unknown_switches;

        for (int i = 0; i < N; i++){
            if (solved_door[i] == -1){
                unknown_switches.push_back(i);
            }
        }

        int current_door_position = 0;
        int S[N];
        for (int i = 0; i < N; i++){
            if (solved_position[i] == -1){
                S[i] = 0;
            } else {
                S[i] = solved_position[i];
            }
        }

        int d = tryCombination(S);
        if (d >= 0 && d <= current_door){
            current_door_position = 1;
        }

        int low = 0;
        int high = unknown_switches.size() - 1;


        //answer in [low, high]
        while (high != low){
            int mid = (high + low) / 2;

            for (int i = 0; i < N; i++){
                if (solved_position[i] == -1){
                    S[i] = current_door_position;
                } else {
                    S[i] = solved_position[i];
                }
            }

            for (int i = low; i <= mid; i++){
                S[unknown_switches[i]] = ((current_door_position + 1) % 2);
            }

            d = tryCombination(S);

            if (d == current_door ){
                high = mid;
            } else {
                low = mid + 1;
            }

        }

        solved_door[unknown_switches[low]] = current_door;
        solved_position[unknown_switches[low]] = current_door_position;


    }


    answer(&solved_position[0], &solved_door[0]);

}

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