Submission #153775

#	Time	Username	Problem	Language	Result	Execution time	Memory
153775		jhwest2	Cave (IOI13_cave)	C++14	0 / 100	9 ms	640 KiB

cave

#include <bits/stdc++.h>
using namespace std;
#include "cave.h"

int Q[5050], S[5050];
int ans[5050], where[5050];
void exploreCave(int N) {
    for (int i=0; i<N; i++) ans[i] = -1;

    for (int i=0; i<N; i++) {
    	for (int j=0; j<N; j++) {
    		if (ans[j] == -1) Q[j] = 0;
    		else Q[j] = ans[j];
    	}
    	int A = tryCombination(Q);

    	for (int j=0; j<N; j++) {
    		if (ans[j] == -1) Q[j] = 1;
    		else Q[j] = ans[j];
    	}
    	int B = tryCombination(Q), C = A<B;


    	int cnt = 0;
    	for (int j=0; j<N; i++) {
    		if (ans[j] == -1) S[cnt++] = j;
    	}

    	int lo=0, hi=cnt-1;
    	while (lo<hi) {
    		int mid = lo+hi>>1;
    		for (int j=0; j<N; j++) {
    			if (ans[j] != -1) Q[j] = ans[j];
    			else {
    				if (S[lo]<=j && j<=S[mid]) Q[j] = C;
    				else Q[j] = !C;
    			}
    		}

    		int tmp = tryCombination(Q);
    		if (tmp > i) hi = mid;
    		else lo = mid+1;
    	}

    	where[i] = lo;
    	ans[i] = C;
    }

    answer(ans, where);
}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:31:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
       int mid = lo+hi>>1;
                 ~~^~~

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