Submission #446337

#	Time	Username	Problem	Language	Result	Execution time	Memory
446337		mickytanawin	Cave (IOI13_cave)	C++17	100 / 100	307 ms	452 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 PERMU\n";
        for(int j = 0; j < N; ++j){
            cout << permu[j] << ' ';
        }
        printf("check:%d\n", tryCombination(permu));*/
        if(isOpen(i, tryCombination(permu))){
            correct = 0;
        } else {
            correct = 1;
        }
        //printf("correct:%d\n", correct);
        //cout << '\n';
        int l = 0;
        int r = N - i - 1;
        while(l < r){
            //printf("l:%d r:%d\n", l, r);
            int m = (l + r) / 2;
            for(int j = l; j <= m; ++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;
            } else {
                for(int j = l; j <= m; ++j){
                    permu[switches[j]] = correct ^ 1;
                }
                l = m + 1;
            }
        }
        //printf("door[%d]:%d\n", i, switches[l]);
        ansP[switches[l]] = correct;
        permu[switches[l]] = correct;
        ansD[switches[l]] = i;
        swap(switches[l], 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: 12 / 12
• Subtask 2: 13 / 13
• Subtask 3: 21 / 21
• Subtask 4: 30 / 30
• Subtask 5: 24 / 24