Submission #154459

#	Time	Username	Problem	Language	Result	Execution time	Memory
154459		songc	Cave (IOI13_cave)	C++14	100 / 100	418 ms	576 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
 
int N;
int S[5050];
int ans[5050];
 
void exploreCave(int n) {
    N = n;
    memset(ans, -1, sizeof ans);
    for (int i=0; i<N; i++){
    	bool st = (i == tryCombination(S));
    	int l = 0, r=N-1;
    	while (l < r){
    		int mid = (l+r)/2;
    		for (int i=l; i<=mid; i++) if (ans[i] == -1) S[i] = 1;
    		bool ret = (i == tryCombination(S));
            for (int i=l; i<=mid; i++) if (ans[i] == -1) S[i] = 0;
    		if (st == ret) l = mid+1;
    		else r = mid;
    	}
    	ans[l] = i;
    	if (st) S[l] = 1;
    }
    answer(S, ans);
}

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