Submission #1029963

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029963		tolbi	Cave (IOI13_cave)	C++17	100 / 100	218 ms	656 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
//int tryCombination(int S[]);\
void answer(int S[], int D[]);

void exploreCave(int N) {
    int S[N];
    int D[N];
    vector<int> unknown(N);
    iota(unknown.begin(), unknown.end(), 0);
    int sor[N];
    for (int i = 0; i < N; ++i)
    {
        sor[i]=0;
    }
    int last = tryCombination(sor);
    for (int i = 0; i < N; i++){
        int l = 0, r = unknown.size()-1;
        while (l<r){
            int mid = l+(r-l)/2;
            for (int j = 0; j <= mid; j++){
                sor[unknown[j]]=1;
            }
            int x = tryCombination(sor);
            if ((x==i)!=(last==i)){
                r=mid;
            }
            else {
                l=mid+1;
            }
            for (int j = 0; j <= mid; j++){
                sor[unknown[j]]=0;
            }
        }
        S[unknown[l]]=i;
        if (last==i) {
            D[unknown[l]]=1;
            sor[unknown[l]]=1;
            last = tryCombination(sor);
        }
        else D[unknown[l]]=0;
        swap(unknown[l],unknown.back());
        unknown.pop_back();
    }
    answer(D,S);
}

Compilation message (stderr)

cave.cpp:4:1: warning: multi-line comment [-Wcomment]
    4 | //int tryCombination(int S[]);\
      | ^

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