Submission #883464

#	Time	Username	Problem	Language	Result	Execution time	Memory
883464		theghostking	Cave (IOI13_cave)	C++17	100 / 100	274 ms	856 KiB

cave

#include "cave.h"

void exploreCave(int N) {
    /* ... */
	int sw[N]; //sw[i] -> orientation of ith switch
	int dw[N]; //dw[i] -> door that switch i is connected to
	for (int i = 0; i<N; i++){
	    sw[i] = 0;
	    dw[i] = -1;
	}
	for (int k = 0; k<N; k++){
	    //find switch to kth door
	    for (int i = 0; i<N; i++){
	        if (dw[i] == -1){
	            sw[i] = 0;
	        }
	    }
	    int res = tryCombination(sw);
	    int ori = 1;
	    if (res > k || res == -1){
	        ori = 0;
	    }
	    //now find range
	    int lo = 0;
	    int hi = N-1;
	    int mid;
	    int ind;
	    while (lo <= hi){
	        if (lo == hi){
	            ind = lo;
	            break;
	        }
	        mid = (lo + hi)/2;
	        //check lo...mid
	        for (int i = lo; i<=mid; i++){
	            if (dw[i] == -1){
	                sw[i] = ori;
	            }
	        }
	        for (int i = mid+1; i<=hi; i++){
	            if (dw[i] == -1){
	                sw[i] = 1-ori;
	            }
	        }
	        res = tryCombination(sw);
	        if (res > k || res == -1){
	            //in this range
	            ind = lo;
	            hi = mid;
	        }
	        else{
	            lo = mid + 1;
	        }
	    }
	    dw[ind] = k;
	    sw[ind] = ori;
	}
	answer(sw,dw);
}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:56:14: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
   56 |      sw[ind] = ori;
      |      ~~~~~~~~^~~~~

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