제출 #423878

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
423878		ioi	동굴 (IOI13_cave)	C++14	100 / 100	373 ms	464 KiB

cave

#include "cave.h"
#include<bits/stdc++.h>
using namespace std ;

void exploreCave(int N) {
//int main(){
   // int N = 4 ;

    int com[N] , ans[N];
    memset(com , 0 , sizeof com);
    int anscom[N];

    memset(anscom , 0 , sizeof anscom);


    for(int i = 0 ; i < N ; i ++){
        int c = tryCombination(com);
        if(c != i){
            for(int j = 0 ; j < N ; j ++){
                if(!anscom[j])com[j] ^= 1 ;

            }


        }
        int l = 0 , r = N - 1 , md ;
        c = i ;


        while(l < r){


            md = (l + r) / 2 ;

            for(int j = l ; j <= md ; j ++){
                if(!anscom[j])com[j] ^= 1 ;

            }

            int c2 = tryCombination(com);
            for(int j = l ; j <= md ; j ++){
                if(!anscom[j])com[j] ^= 1 ;

            }
            if(c == c2)l = md + 1 ;
            else r = md ;



        }
       // cout << "l is " << l << endl ;
        anscom[l] ++ ;
        ans[l] = i ;
        com[l] ^= 1 ;

    }
    answer(com , ans);
   // for(int i = 0 ; i < N ; i ++)cout << com[i] << " " << ans[i] << endl ;
}

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