Submission #670967

#	Time	Username	Problem	Language	Result	Execution time	Memory
670967		1bin	Cave (IOI13_cave)	C++14	100 / 100	300 ms	564 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;
int s[4] = {1, 1, 1, 0};
int d[4] = {2, 1, 3, 0};

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

/*
int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    int N;
    cin >> N;
    exploreCave(N);
    return 0;
}*/

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