Submission #210381

#	Time	Username	Problem	Language	Result	Execution time	Memory
210381		tatyam	Cave (IOI13_cave)	C++17	100 / 100	327 ms	640 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
using uint = unsigned;
#define rep(n) for(int i = 0; i < n; i++)
#define each(i,a) for(auto&& i : a)
#define all(a) begin(a), end(a)


int n;
int s[5000], d[5000];
int flag, x;
vector<int> candidate;
bool query(){
    uint a = tryCombination(s);
    return a > x;
}
auto find(vector<int>::iterator begin, vector<int>::iterator end){
    if(end - begin == 1) return begin;
    auto cen = begin + (end - begin) / 2;
    for(auto p = begin; p < cen; p++) s[*p] = flag;
    for(auto p = cen; p < end; p++) s[*p] = !flag;
    if(query()) return find(begin, cen);
    else return find(cen, end);
}
void find(int _x){
    x = _x;
    each(i, candidate) s[i] = 1;
    flag = query();
    auto p = find(all(candidate));
    d[*p] = x;
    s[*p] = flag;
    candidate.erase(p);
}
void exploreCave(int N){
    n = N;
    candidate.resize(n);
    iota(all(candidate), 0);
    rep(n) find(i);
    answer(s, d);
}

Compilation message (stderr)

cave.cpp: In function 'bool query()':
cave.cpp:16:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     return a > x;
            ~~^~~

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