제출 #917175

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

cave

#include "cave.h"

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

void exploreCave(int N) {
    
    /* ... */
    
    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 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;
        
        
        
        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-1;
            
            
        }
        
        switch_of_door[door]=l;
        correct_pos_of_switch[l]=correct_pos_of_door[door];
        combination[l]=correct_pos_of_door[door];
        
        
    }
    
    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