제출 #446324

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
446324		mickytanawin	동굴 (IOI13_cave)	C++17	51 / 100	269 ms	440 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
 
bool isOpen(int i, int ret){
    return ret == -1 || ret > i;
}
 
void exploreCave(int N){
    int switches[N], permu[N], ansD[N], ansP[N];
    for(int i = 0; i < N; ++i){
        switches[i] = i;
        permu[i] = 0;
        ansP[i] = 0;
        ansD[i] = 0;
    }
    for(int i = 0; i < N; ++i){
        for(int j = 0; j < N - i; ++j){
            permu[switches[j]] = 0;
        }
        int correct;
        /*cout << "PRINT SWITCHES\n";
        for(int j = 0; j < N; ++j){
            cout << switches[j] << ' ';
        }
        cout << '\n';
        printPermu(permu, N);
        printf("check:%d\n", tryCombination(permu));*/
        if(isOpen(i, tryCombination(permu))){
            correct = 0;
        } else {
            correct = 1;
        }
        //printf("correct:%d\n", correct);
        int l = 0;
        int r = N - i - 1;
        int ans = 0;
        while(l <= r){
            //printf("l:%d r:%d\n", l, r);
            int m = (l + r) / 2;
            for(int j = l; j <= r; ++j){
                permu[switches[j]] = correct ^ 1;
            }
            permu[switches[m]] = correct;
            if(isOpen(i, tryCombination(permu))){
                ans = m;
                break;
            }
            //permu[switches[m]] = correct ^ 1;
            for(int j = l; j <= m - 1; ++j){
                permu[switches[j]] = correct;
            }
            for(int j = m + 1; j <= r; ++j){
                permu[switches[j]] = correct ^ 1;
            }
            if(isOpen(i, tryCombination(permu))){
                r = m - 1;
            } else {
                /*for(int j = l; j <= m; ++j){
                    permu[switches[j]] = correct ^ 1;
                }*/
                l = m + 1;
            }
        }
        //printf("ans:%d door[%d]:%d\n", ans, i, switches[ans]);
        ansP[switches[ans]] = correct;
        permu[switches[ans]] = correct;
        ansD[switches[ans]] = i;
        swap(switches[ans], switches[N - i - 1]);
        /*cout << "ansP: ";
        for(int j = 0; j < N; ++j){
            cout << ansP[j] << ' ';
        }
        cout << "\nansD: ";
        for(int j = 0; j < N; ++j){
            cout << ansD[j] << ' ';
        }
        cout << '\n';*/
    }
    answer(ansP, ansD);
}

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