Submission #990812

#	Time	Username	Problem	Language	Result	Execution time	Memory
990812		ChottuF	Cave (IOI13_cave)	C++17	100 / 100	184 ms	600 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:18: 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