#include "cave.h"

void exploreCave(int n){
    int test[n];
    int sta[n];
    int lnk[n];
    int ans, l, r, m, cor, l2, r2;

    for(int i = 0; i<n; ++i){
        sta[i] = -1;
        lnk[i] = -1;
    }

    for(int i = 0; i<n; ++i){

        //std::cout << i << " YOoo \n";

        cor = 0;

        for(int j =0; j<n; ++j){
            if(sta[j]!=-1){
                test[j]=sta[j];
            }
            else{
                test[j] = cor;
            }
        }

        l=0;
        r=n-1;

        m=(l+r)/2;

        ans = tryCombination(test);

        if(ans==-1 || ans>i){
            //open

            //Leave l-m wrong
            for(int j = l; j<=m; ++j){
                if(sta[j]!=-1){
                    test[j]=sta[j];
                }
                else{
                    test[j] = !cor;
                }
            }
        }
        else{
            //closed
            cor=!cor;
            //Leave m+1-r correct
            for(int j = m+1; j<=r; ++j){
                if(sta[j]!=-1){
                    test[j]=sta[j];
                }
                else{
                    test[j] = cor;
                }
            }
        }

        while(l!=r){

            for(int j = 0; j<n; ++j){
                //std::cout << test[j]<< ' ';
            }
            //std::cout << "cor: " << cor << ' '<<l << ' '<< r << ' ' << i << "  \n";

            ans = tryCombination(test);

            m=(l+r)/2;

            if(ans==-1 || ans>i){
                //open
                //must be in m+1-r
                l=m+1;
                m=(l+r)/2;
                for(int j = l; j<=m; ++j){
                    if(sta[j]!=-1){
                        test[j]=sta[j];
                    }
                    else{
                        test[j] = !cor;
                    }
                }
            }
            else{
                //closed
                for(int j = m+1; j<=r; ++j){
                    if(sta[j]!=-1){
                        test[j]=sta[j];
                    }
                    else{
                        test[j] = !cor;
                    }
                }
                r=m;
                m=(l+r)/2;
                for(int j = m+1; j<=r; ++j){
                    if(sta[j]!=-1){
                        test[j]=sta[j];
                    }
                    else{
                        test[j] = cor;
                    }
                }

            }
        }

        //std::cout <<  l <<  ':' << cor << '\n';

        sta[l]=cor;
        lnk[l]=i;

    }

    answer(sta, lnk);

    return;
}