Submission #988726

#	Time	Username	Problem	Language	Result	Execution time	Memory
988726		lalig777	Cave (IOI13_cave)	C++14	100 / 100	168 ms	600 KiB

cave

#include"cave.h"
#include <iostream>
#include <vector>
using namespace std;


void exploreCave(int N){
    bool confirmat[N]={false};
    int comb[N]={0};
    int porta[N]={-1};
    bool funcionaba, funciona;
    int act;
    for (int i=0; i<N; i++){
        int doorsleft=N-i, left=0, right=N-1;
        for (int i=0; i<N; i++){
            if (confirmat[i]!=true){
                left=i;
                break;
            }
        }for (int i=N-1; i>=0; i--){
            if (confirmat[i]!=true){
                right=i;
                break;
            }
        }act=tryCombination(comb);
        if (act!=i) funcionaba=true;
        else funcionaba=false;
        int r=N-1;
        while (left!=right){
            int sobra=doorsleft%2;
            doorsleft/=2;
            int j=doorsleft;
            for (int i=left; i<=right; i++){
                if (confirmat[i]==true) continue;
                else{
                    j--;
                    comb[i]=1-comb[i];
                    if (j==0){
                        r=i;
                        break;
                    }
                }
            }
            act=tryCombination(comb);
            if (act!=i) funciona=true;
            else funciona=false;
            if (funciona!=funcionaba){
                right=r;
            }else{
                doorsleft+=sobra;
                for (int i=r+1; i<N; i++){
                    if (confirmat[i]!=true){
                        left=i;
                        break;
                    }
                }
            }funcionaba=funciona;
        }if (funcionaba==false) comb[left]=1-comb[left];
        confirmat[left]=true;
        porta[left]=i;
    }answer(comb, porta);
}

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