Submission #956049

#	Time	Username	Problem	Language	Result	Execution time	Memory
956049		MuntherCarrot	Cave (IOI13_cave)	C++14	100 / 100	265 ms	864 KiB

cave

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

using namespace std;

// int tryCombination(int S[]);
// void answer(int S[], int D[]);

#define ask(x) tryCombination(x)
#define submit(x, y) answer(x, y)

const int MAXN = 5010;
int done[MAXN];
bool pos[MAXN];
int n;

void solve(int x, vector<int> &vec){
    int a[n] = {};
    for(int i = 0; i < n; i++){
        if(done[i] == -1) continue;
        a[i] = pos[done[i]];
    }
    int l = 0, r = vec.size() - 1;
    pos[x] = (ask(a) == x); // 1 = colse, 0 = open
    while(l < r){
        int mid = (l + r) / 2;
        // [l, mid], [mid + 1, r]
        for(int i = l; i <= mid; i++){
            a[vec[i]] = 1;
        }
        int res = (ask(a) == x);
        if(res == pos[x]){
            l = mid + 1;
        }
        else{
            r = mid;
        }
        for(int i = l; i <= mid; i++){
            a[vec[i]] = 0;
        }
    }
    done[vec[l]] = x;
    // cout << vec[l] << ' ' << (ask(a) != pos[x] ? "yes" : "no") << endl;
}

void exploreCave(int N){
    memset(done, -1, sizeof done);
    n = N;
    for(int i = 0; i < n; i++){
        vector<int> vec;
        for(int j = 0; j < n; j++){
            if(done[j] != -1) continue;
            vec.push_back(j);
        }
        solve(i, vec);
    }
    int ans1[n], ans2[n];
    for(int i = 0; i < n; i++){
        ans1[i] = pos[done[i]];
        ans2[i] = done[i];
    }
    submit(ans1, ans2);
}

// by me

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