제출 #1360701

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1360701		pcheloveks	동굴 (IOI13_cave)	C++20	100 / 100	111 ms	608 KiB

cave

#include "cave.h"

#include <bits/stdc++.h>

using namespace std;

const int DIM = 5007;

vector < int > undetermined;
int S[DIM], D[DIM];

int comb[DIM];

void exploreCave(int N) {

    for(int i = 0; i < N; i++) {
        S[i] = -1; D[i] = -1;
        undetermined.push_back(i);
    }

    int firstDoor = 0;

    while(undetermined.size() > 0) {
        for(int i = 0; i < N; i++) {
            if(S[i] != -1) comb[i] = S[i];
            else comb[i] = 0;
        }

        int door = tryCombination(comb);

        if(door == firstDoor) {
            // firstDoor --- open

            int L = -1, R = undetermined.size();
            while(R - L > 1) {
                int mid = (L + R) >> 1;

                for(int i = 0; i <= mid; i++) comb[undetermined[i]] = 1;
                for(int i = mid + 1; i < undetermined.size(); i++) comb[undetermined[i]] = 0;

                door = tryCombination(comb);

                if(door == firstDoor) L = mid;
                else R = mid;
            }

            D[undetermined[R]] = firstDoor;
            S[undetermined[R]] = 1;

            vector < int > tmp;
            for(int i = 0; i < undetermined.size(); i++) {
                if(i == R) continue;
                tmp.push_back(undetermined[i]);
            }
            undetermined = tmp;
        }
        else {
            // firstDoor --- closed

            int L = -1, R = undetermined.size();
            while(R - L > 1) {
                int mid = (L + R) >> 1;

                for(int i = 0; i <= mid; i++) comb[undetermined[i]] = 1;
                for(int i = mid + 1; i < undetermined.size(); i++) comb[undetermined[i]] = 0;

                door = tryCombination(comb);

                if(door != firstDoor) L = mid;
                else R = mid;
            }

            D[undetermined[R]] = firstDoor;
            S[undetermined[R]] = 0;

            vector < int > tmp;
            for(int i = 0; i < undetermined.size(); i++) {
                if(i == R) continue;
                tmp.push_back(undetermined[i]);
            }
            undetermined = tmp;
        }
        firstDoor++;
    }

    answer(S, D);
}

• 서브태스크 1: 12 / 12
• 서브태스크 2: 13 / 13
• 서브태스크 3: 21 / 21
• 서브태스크 4: 30 / 30
• 서브태스크 5: 24 / 24