Submission #319157

#	Time	Username	Problem	Language	Result	Execution time	Memory
319157		lohacho	Cave (IOI13_cave)	C++14	100 / 100	376 ms	744 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>

using namespace std;

using LL = long long;
const int MOD = (int)1e9 + 7;
const int NS = (int)5004;
int N;
int S[NS], D[NS], chk[NS];
vector<int> need;

void exploreCave(int Nin) {
    N = Nin;
    for(int i = 0; i < N; ++i){
        int pos = tryCombination(S);
        if(pos == -1){
            pos = MOD;
        }
        int nows;
        if(pos > i){
            nows = 0;
        }
        else{
            nows = 1;
        }
        need.clear();
        for(int j = 0; j < N; ++j){
            if(!chk[j]){
                need.push_back(j);
            }
        }
        int low = 0, high = (int)need.size() - 1, mid;
        while(low < high){
            mid = (low + high) >> 1;
            if(nows){
                for(int j = low; j <= mid; ++j){
                    S[need[j]] = 1;
                }
            }
            else{
                for(int j = mid + 1; j <= high; ++j){
                    S[need[j]] = 1;
                }
            }
            int rv = tryCombination(S);
            if(rv == -1){
                rv = MOD;
            }
            if(nows){
                for(int j = low; j <= mid; ++j){
                    S[need[j]] = 0;
                }
            }
            else{
                for(int j = mid + 1; j <= high; ++j){
                    S[need[j]] = 0;
                }
            }
            if(rv > i){
                high = mid;
            }
            else{
                low = mid + 1;
            }
        }
        S[need[low]] = nows;
        D[need[low]] = i;
        chk[need[low]] = 1;
    }
    answer(S, D);
}

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