Submission #1310766

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310766		jinjikhadzegiorgi	Cave (IOI13_cave)	C++20	12 / 100	227 ms	508 KiB

cave

#include "cave.h"

void exploreCave(int n) {
    // create s, sFinal, dFinal and found arrays
	int s[n], sFinal[n], dFinal[n];
    bool found[n];
    
    // assign starting value to s and found, 0 to both 
    for(int i=0; i<n; i++){
    	s[i]=0;
    	found[i]=false;
	}
	
	
	// start finding which swich opens door i
	for(int i=0; i<n; i++){
		// reset the ones that we didnt explore
		for(int j=0; j<n; j++){
			if(!found[j])s[j]=0;
		}
		
		// check if ith door will open
		int res=tryCombination(s);
		int targetState;
		if(res==-1 || res>i){
			// if yes, set val to 0
			targetState=0;
		}else{
			// if nah, set val to 1
			targetState=1;
		}
		
		// left, right, and switch for ith door
		int l=0; int r=n-1; int swch=-1;
		while(l<=r){
			// find middle
			int m=(l+r)/2;
			// set all unexplored switches in left half
			for(int j=i; j<n; j++){
				if(!found[j]){
					if(j>=l && j<=m){
						s[j]=targetState;
					}else{
						s[j]=1-targetState;
					}
				}
			}
			// check in which half our switch is located at
			int res2=tryCombination(s);
			if(res2==-1 || res2>i){
				r=m-1;
				swch=m;
			}else{
				l=m+1;
			}
			
		}
		
		// update found, sFinal, dFinal and s arrays
		found[swch]=true;
		sFinal[swch]=targetState;
		dFinal[swch]=i;
		s[swch]=targetState;
		
		
	}
	// print answer
	answer(sFinal, dFinal);
    
    
}

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