Submission #367644

#	Time	Username	Problem	Language	Result	Execution time	Memory
367644		Pulgster	Cave (IOI13_cave)	C++17	34 / 100	2095 ms	1692 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
#define imie(...) " [" << #__VA_ARGS__ ": "<< (__VA_ARGS__) << "] "
#define ed <<endl
const int op = 1;
const int cl = 0;
void exploreCave(int n) {
   	int cur[n];
   	int fixed[n];
   	int mat[n];
   	for(int i=0;i<n;i++){
   		cur[i] = fixed[i] = mat[i] = 0;
   	}
    for(int i=0;i<n;i++){
    	int temp = tryCombination(cur);
    	int st;
    	if(temp == -1 or temp > i){
    		st = op;
    	} else{
    		st = cl;
    	}
    	// cerr << imie(i) imie(temp) imie(st) ed;
    	if(st == op){
    		int lo = 0;
    		int hi = n-1;
    		while(hi != lo){
    			int mid = lo + ((hi-lo)/2);
    			// cerr << imie(i) << imie(st) << imie(hi) << imie(lo) << imie(mid) ed;
    			int me[n];
    			for(int j=0;j<n;j++){
    				me[j] = cur[j];
    			}
    			for(int j=lo;j<=mid;j++){
    				if(!fixed[j]){
    					me[j] = !cur[j];
    				}
    			}
    			int res = tryCombination(me);
    			// im trying the left part;
    			if(res == i){
    				hi = mid;
    			} else{
    				lo=mid+1;
    			}
    		}
    		cur[hi]=0;
    		fixed[hi]=1;
    		mat[hi] = i;
    	} else{
    		int lo = 0;
    		int hi = n-1;
    		while(hi != lo){
    			int mid = lo + ((hi-lo)/2);
    			
    			int me[n];
    			for(int j=0;j<n;j++){
    				me[j] = cur[j];
    			}
    			for(int j=lo;j<=mid;j++){
    				if(!fixed[j]){
    					me[j] = !cur[j];
    				}
    			}
    			for(int i =0;i<n;i++){
    				cerr << me[i] << ' ';
    			}
    			cerr ed;
    			int res = tryCombination(me);
    			// cerr << imie(i) << imie(st) << imie(hi) << imie(lo) << imie(mid) << imie(res);
    			// im trying the left part;
    			if(res != i){
    				hi = mid;
    			} else{
    				lo=mid+1;
    			}
    		}
    		// cerr << imie(hi) imie(i) ed;
    		cur[hi]=1;
    		fixed[hi]=1;
    		mat[hi]=i;
    	}
    }
    answer(cur, mat);
}

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