Submission #410813

#	Time	Username	Problem	Language	Result	Execution time	Memory
410813		Christopher_Rdz	Cave (IOI13_cave)	C++14	100 / 100	1018 ms	532 KiB

cave

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

int a[5005];
int b[5005];
int S[5005];
int puerta[5005];

void exploreCave(int N){
    int res;
    for (int i = 0; i < N; i++){
        a[i] = -1;
        b[i] = -1;
    }
    for (int i = 0; i < N; i++){
        for (int j = 0; j < N; j++){
            if (a[j] != -1){
                S[j] = a[j]; 
            }else{
                S[j] = 1;
            }
        }
        res = tryCombination(S);
        if (res > i or res == -1){
            puerta[i] = 1;
        }else{
            puerta[i] = 0;
        }
        int ini = 0;
        int fin = N;
        int mit = (ini + fin) / 2;
        while(ini != mit){
            for (int j = 0; j < mit; j++){
                if (a[j] != -1){
                    S[j] = a[j];
                }else{
                    S[j] = puerta[i];
                }
            }
            for (int j = mit; j < N; j++){
                if (a[j] != -1){
                    S[j] = a[j];
                }else{
                    S[j] = 1 - puerta[i];
                }
            }
            res = tryCombination(S);
            if (res > i or res == -1){
                fin = mit;
                mit = (ini + fin) / 2;
            }else{
                ini = mit;
                mit = (ini + fin) / 2;
            }
        }
        a[mit] = puerta[i];
        b[mit] = i;
    }
    answer(a, b);
}

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