Submission #168678

#	Time	Username	Problem	Language	Result	Execution time	Memory
168678		Shafin666	Cave (IOI13_cave)	C++14	100 / 100	1295 ms	640 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"
#define pb push_back
#define pii pair<int, int>
#define nyan "(=^･ω･^=)"
#define read_input         freopen("in.txt","r", stdin)
#define print_output       freopen("out.txt","w", stdout)
typedef long long ll;
typedef long double ld;
using namespace std;

int n;

void filter(int *a, int *b) {
	for(int i = 0; i < n; i++) 
		if(b[i] != -1) a[i] = b[i];
}

void flip(int *a, int l, int r) {
	for(int i = l; i <= r; i++) a[i] ^= 1;
}

void exploreCave(int N) {
	n = N;
    //tryCombination(a);

    int a[N], b[N], D[N];

    memset(b, -1, sizeof b);

    for(int i = 0; i < N-1; i++) {
    	int t1 = i+1;
    	
    	memset(a, 0, sizeof a);
    	filter(a, b);
    	
    	int check = tryCombination(a);
    	int x = 0;

    	if(check != -1 && check < t1) { // i'th gate does not open with 0
    		flip(a, 0, n-1);
    		filter(a, b);
    		x = 1;
    	}  

    	memset(a, 0, sizeof a);
    	if(x) flip(a, 0, n-1);

    	int lo = 0, hi = n-1;
    	while(lo < hi) {
    		int mid = lo + hi >> 1;

    		flip(a, lo, mid); filter(a, b);

    		int t2 = tryCombination(a);

 			if(t2 >= t1 || t2 == -1) lo = mid+1;
 			else {
 				hi = mid;
 				flip(a, lo, mid);
 			}
    	}
 
    	b[lo] = a[lo]; // correct direction of switch of i'th door
    	D[lo] = i;
    }

    int hole; 
    for(int i = 0; i < n; i++) if(b[i] == -1) hole = i;
    memset(a, 0, sizeof a); filter(a, b);
    int check = tryCombination(a);

    if(check == -1) b[hole] = 0;
    else b[hole] = 1;

    D[hole] = n-1;


    /*for(int i = 0; i < n; i++) {
    	b[i] ^= 1;
    	D[i] = tryCombination(b);
    	b[i] ^= 1;
    }*/

    answer(b, D);
}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:51:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
       int mid = lo + hi >> 1;
                 ~~~^~~~
cave.cpp:76:13: warning: 'hole' may be used uninitialized in this function [-Wmaybe-uninitialized]
     D[hole] = n-1;
     ~~~~~~~~^~~~~

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