Submission #670964

#	Time	Username	Problem	Language	Result	Execution time	Memory
670964		1bin	Cave (IOI13_cave)	C++14	0 / 100	199 ms	408 KiB

cave

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

#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 5e3 + 5;
int N, S[NMAX], D[NMAX], fix[NMAX], x, y;

void exploreCave(int N){
    for(int i = 0; i < N; i++){
        for(int t = 0; t < 2; t++){
            for(int j = 0; j < N; j++)
                if(!fix[j]) S[j] = t;
            y = tryCombination(S);
            if(y == -1 || y > i) {
                x = t; break;
            }
        }
        int l = 0, r = N - 1, m;
        while(l < r){
            m = (l + r + 1) / 2;
            for(int i = l; i < m; i++) if(!fix[i]) S[i] = x;
            for(int i = m; i <= r; i++) if(!fix[i]) S[i] = !x;
            y = tryCombination(S);
            if(y == -1 || y < m) r = m - 1;
            else l = m;
        }
        S[l] = x; D[l] = i;
        fix[l] = 1;
    }
    answer(S, D);
    return;
}   

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