Submission #1310808

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310808		jinjikhadzegiorgi	Cave (IOI13_cave)	C++20	100 / 100	509 ms	516 KiB

cave

#include "cave.h"

void exploreCave(int n) {
    
	int s[n], sFinal[n], dFinal[n];
    bool found[n];
    
    for(int i=0; i<n; i++){
    	s[i]=0;
    	found[i]=false;
	}
	
	

	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			if(!found[j])s[j]=0;
		}
		
		int res=tryCombination(s);
		int targetState;
		if(res==-1 || res>i){
			targetState=0;
		}else{
			targetState=1;
		}
		
		int l=0; int r=n-1; int swch=-1;
		while(l<=r){
			int m=(l+r)/2;
			for(int j=0; j<n; j++){
				if(!found[j]){
					if(j>=l && j<=m){
						s[j]=targetState;
					}else{
						s[j]=1-targetState;
					}
				}
			}
			int res2=tryCombination(s);
			if(res2==-1 || res2>i){
				r=m-1;
				swch=m;
			}else{
				l=m+1;
			}
			
		}
		
		found[swch]=true;
		sFinal[swch]=targetState;
		dFinal[swch]=i;
		s[swch]=targetState;
		
		
	}
	answer(sFinal, dFinal);
    
    
}

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