제출 #917313

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

cave

#include "cave.h"
#include "bits/stdc++.h"
using namespace std;
void exploreCave(int N) {
    
    /* ... */
    
    int correct_pos_of_door[N];
    int door_of_switch[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(door_of_switch,-1,sizeof door_of_switch);
    

    
    //lets try to find correct pos of 1 door and correct pos of switch corresponding to it
    
    int combination[N];
    for(int i=0;i<N;i++) combination[i]=0;
    
    for(int door=0;door<N;door++){
        
        int l=0,r=N-1;
        
        int res=tryCombination(combination);
        
        if(res==door) correct_pos_of_door[door]=1;
        else correct_pos_of_door[door]=0;
        
        int ind;
        
    
        while(l<r){
            
            int m=(l+r)/2;
         
            
       
            
            //either my switch corresponding to door will be in left part or right part
            
        
            int temp[N];
            for(int i=0;i<N;i++) temp[i]=combination[i];
            
            //making left to be correct
            
            if(correct_pos_of_door[door]){
 
                for(int i=l;i<=m;i++){
                    if(correct_pos_of_switch[i]==-1) temp[i]=1;
                }
                
                
            }
            else{
                for(int i=m+1;i<=r;i++){
                    if(correct_pos_of_switch[i]==-1) temp[i]=1;
                }
            }
            
            res=tryCombination(temp);
          
            if(res==door){
                l=m+1;
            } 
            else{
               r=m;  
            } 
            
            
        }
        
        ind=l;
        
      
    
        
        
        door_of_switch[ind]=door;
        correct_pos_of_switch[ind]=correct_pos_of_door[door];
        combination[ind]=correct_pos_of_door[door];
      
              
        
    }
    

    answer(correct_pos_of_switch,door_of_switch);
    
    
    
    
    
}

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