Submission #153776

#	Time	Username	Problem	Language	Result	Execution time	Memory
153776		jhwest2	Cave (IOI13_cave)	C++14	100 / 100	1304 ms	648 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;

    	if (A==-1 || (A>B && B!=-1)) C=0;
    	else C = 1;


    	int cnt = 0;
    	for (int j=0; j<N; j++) {
    		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 || tmp == -1) hi = mid;
    		else lo = mid+1;
    	}

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

    answer(ans, where);
}

Compilation message (stderr)

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

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