제출 #917171

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
917171		_VIBE	동굴 (IOI13_cave)	C++17	0 / 100	90 ms	600 KiB

cave

#include "cave.h"

#include<bits/stdc++.h>


void exploreCave(int N) {
    
    /* ... */
    using namespace std;
    int correct_pos_of_door[N];
    int switch_of_door[N];
    int correct_pos_of_switch[N];
    memset(correct_pos_of_switch,-1,sizeof correct_pos_of_switch);
    memset(correct_pos_of_door,-1,sizeof correct_pos_of_door);
    memset(switch_of_door,-1,sizeof switch_of_door);
    
    
    
    
    //lets try to find correct pos of 1 door and correct pos of switch corresponding to it
    
    int combi[N];
    for(int i=0;i<N;i++) combi[i]=0;
    
    for(int door=0;door<N;door++){
        
        int switch_range_l=0,switch_range_r=N-1;
        
        int res=tryCombination(combi);
        
        if(res==door) correct_pos_of_door[door]=1;
        else correct_pos_of_door[door]=0;
        
        
        
        while(switch_range_l!=switch_range_r){
            int m=(switch_range_l+switch_range_r)/2;
            
            //either my switch corresponding to door will be in left part or right part
            
            //making all left part one for positions i dont know in left part
            int temp[N];
            for(int i=0;i<N;i++) temp[i]=combi[i];
            
            if(correct_pos_of_door[door]){

                for(int i=switch_range_l;i<=m;i++){
                    if(correct_pos_of_switch[i]==-1) temp[i]=1;
                }
                
                
            }
            else{
                for(int i=m+1;i<=switch_range_r;i++){
                    if(correct_pos_of_switch[i]==-1) temp[i]=1;
                }
            }
            
            res=tryCombination(temp);
            
            if(res==door) switch_range_l=m+1;
            else switch_range_r=m-1;
            
            
        }
        
        switch_of_door[door]=switch_range_l;
        correct_pos_of_switch[switch_range_l]=correct_pos_of_door[door];
        combi[switch_range_l]=correct_pos_of_switch[switch_range_l];
        
        
    }
    
    answer(correct_pos_of_switch,switch_of_door);
    
    
    
    
    
}

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