avoid — CEOI contest
Task type: interactive | Time limit: 0.25 s | Memory limit: 512 MB | Difficulty: 29
Algorithms: binary search, bitmask, precomputation, heuristics, simulated annealing, constructive

![](_page_0_Picture_0.jpeg)

# How to Avoid Disqualification in 75 Easy Steps (avoid)

You are standing in front of the open safe, a medal in your hand. But your triumph turns to despair as you look around: a message on a tie you found in the room reveals that your assistant exposed your plan to the Scientific Committee! Now the two committee chairmen are hiding in the building to stop you from escaping…

Luckily, you have R vacuum cleaner robots left over from your trade with your fellow contestants. You want to use these robots to locate the two chairmen so that you can avoid them during your escape. You can instruct each robot to scout several of 1000 positions where the chairmen could be located. Unfortunately, the software of these robots is quite simple.* Each robot can only detect whether or not *there is at least one chairman at its scouted positions*.

To make things worse, every robot needs a full hour to scout its positions before returning with its result to you. Because this will drain the robot's battery, *you can send out each robot only once*.

As you don't want to be late for the evening activities, you want to know the positions of the chairmen *after at most H hours*. In particular, you might be forced to send out several robots at once without waiting for the previous robots to return. You can assume that the two chairmen stay at the same positions all the time.†

Write a program which plans this scouting mission and determines where the two chairmen are located.

# Communication

This is a communication task. You must implement the function `std::pair<int, int> scout(int R, int H)` where $R$ and $H$ are as described above. For each testcase, this function is called exactly once and should return a pair of two integers $1 \le a, b \le 1000$ ($a = b$ is allowed), the positions of the two chairmen. Inside `scout`, you can use the following other functions provided by the grader:

*   `void send(std::vector<int> P)` sends a robot to scout the positions `P[0]`, ..., `P[k – 1]` (where `k` is the length of the array `P`). The positions `P[i]` must be pairwise distinct integers between 1 and 1000. You can call this function at most $R$ times per testcase.
*   `std::vector<int> wait()` waits an hour. This function returns an array with exactly one entry for each robot sent out one hour ago (by a call to `send` after the previous call to `wait` or after the beginning of the program). The entry at index `i` is 1 if the `(i + 1)`-th of these robots has detected at least one chairman at its scouted positions, and 0 otherwise. You can call this function at most $H$ times per testcase.

If any of your function calls does not satisfy the above constraints, your program will be immediately terminated and judged as **Not correct** for the respective testcase. You must not write to standard output or read from standard input; otherwise, you may receive the verdict **Security violation!**. You are however free to write to the standard error stream (`stderr`).

You must include the file `avoid.h` in your source code. To test your program locally, you can link it with `sample_grader.cpp`, which can be found in the attachment for this task in cms. See below for a description of the sample grader, and see `sample_grader.cpp` for instructions on how to run it with your program. The attachment also contains a sample implementation as `avoid_sample.cpp`.

<sup>*</sup> After all, you sold all the fancy ones to the other contestants!

<sup>†</sup> Due to the late-night task preparations they are simply too exhausted to move.

![](_page_1_Picture_0.jpeg)

## Constraints and grading

**Subtask 1 (10 points).** $R = 10$, $H = 1$ and both chairmen are located at the same position.

**Subtask 2 (5 points).** $R = H = 20$

**Subtask 3 (10 points).** $R = 30$, $H = 2$

**Subtask 4 (75 points).** $R = 75$, $H = 1$

**Partial scoring.** In Subtask 4, your actual score depends on the maximum number $r_{max}$ of robots sent out over all testcases in this subtask according to the following piecewise linear function:

![](_page_1_Figure_8.jpeg)

In particular, to get full score you must not make more than 26 calls to `send` per testcase in the last subtask. You can also find a table listing all the individual scores in the attachments for this task as `score_table.txt`.

## Example interaction

Consider a testcase with $R = 75$ and $H = 20$ where the chairmen are located at positions 13 and 37. First, the grader calls your function `scout` as `scout(75, 20)`. Then, an interaction between your program and the grader could look as follows:

| Your program       | Return value | Explanation                                                                                                          |
|--------------------|--------------|----------------------------------------------------------------------------------------------------------------------|
| `send({42, 13, 37})` | —            | send a robot to positions 13, 37 and 42                                                                              |
| `send({47, 11})`     | —            | send a robot to positions 11 and 47                                                                                  |
| `wait()`             | `{1, 0}`       | wait an hour for the return of the robots; only<br>the first robot has detected a chairman                           |
| `send({42})`         | —            | send a robot to position 42                                                                                          |
| `wait()`             | `{0}`          | wait an hour; there is no chairman at position 42                                                                    |
| `return {13, 37}`    | —            | you are convinced that the chairmen are located<br>at positions 13 and 37<br>the solution is correct and is accepted |

Returning the pair {37, 13} would be accepted as well. Note that the above queries are of course not sufficient to determine the positions of the chairmen with certainty: For example, both being at position 37 or one chairman being at position 13 while the other is at position 100 would also be consistent with all answers to `wait`, so the grader could also have rejected this solution.

The above interaction is reproduced by `avoid_sample.cpp` on the public testcase.

![](_page_2_Picture_0.jpeg)

## Grader

The sample grader first expects on standard input the integers $R$ and $H$ and the positions $a$ and $b$ of the chairmen ($1 \le a, b \le 1000$). Then, the grader calls `scout(R, H)` and writes to standard output a protocol of all grader functions called by your program. Upon termination, it writes one of the following messages to standard output:

**Invalid input.** The input to the grader via standard input was not of the above format.

**Invalid send.** You called `send` with invalid parameters.

**Out of robots.** You called `send` more than $R$ times.

**Out of time.** You called `wait` more than $H$ times.

**Wrong answer.** The positions returned by `scout` are not the positions of the chairmen.

**Correct:** *r* **robot(s) used,** *h* **hour(s) passed.** The positions returned by `scout` are the positions of the chairmen, there were $r$ calls to `send`, and there were $h$ calls to `wait`.

In contrast, the grader actually used to judge your program will only output **Not correct** (for any of the above errors), **Security violation!**, or **Correct:** *r* **robot(s) used,** *h* **hour(s) passed**. Moreover, the grader is *adaptive*, i.e. the positions of the chairmen may depend on the behavior of your program in the current as well as in earlier runs. Both the sample grader and the grader used to judge your program will terminate your program automatically whenever one of the above errors occurs.

## Limits

Time: 0.25 s
Memory: 512 MiB

Starter code:
grader.cpp: /*
SAMPLE GRADER for task AVOID

USAGE:
place together with your solution and avoid.h in the same directory, then:
g++ <flags> sample_grader.cpp <solution_file>
e.g.:
g++ -std=c++17 sample_grader.cpp avoid.cpp

INPUT/OUTPUT:
The sample grader first expects on standard input the integers R and H and
the positions a and b of the chairmen (1 <= a, b <= 1 000). Then,
the grader calls scout(R, H) and writes to standard output a protocol of all
grader functions called by your program. Upon termination, it writes your
verdict to standard output.
*/
#include <iostream>
#include <set>
#include <vector>

#include "avoid.h"

namespace sample_grader {

using std::cout;
using std::cin;
using std::endl;
using std::set;
using std::swap;
using std::vector;

constexpr int N = 1000;

int R, H;
int r, h;
int a, b;
vector<int> answers;

[[noreturn]] void invalid_input()
{
    cout << "Invalid input" << endl;
    exit(0);
}

[[noreturn]] void wrong_answer(const char *msg)
{
    cout << msg << endl;
    exit(0);
}

void print_vector(vector<int> v)
{
    cout << "{";
    for (size_t i = 0; i < v.size(); ++i) {
        cout <<  v[i];
        if (i + 1 != v.size()) cout << ", ";
    }
    cout << "}";
}

} // namespace sample_grader


void send(std::vector<int> positions)
{
    using namespace sample_grader;
    cout << "send(";
    print_vector(positions);
    cout << ")" << endl;

    ++r;
    if (r > R) wrong_answer("Out of robots");

    set<int> position_set;
    int curr_answer = 0;
    for (int x : positions) {
        if (x < 1 or x > N or position_set.find(x) != position_set.end()) {
            wrong_answer("Invalid send");
        }
        position_set.insert(x);

        if (x == a or x == b) curr_answer = 1;
    }

    answers.push_back(curr_answer);
}

std::vector<int> wait()
{
    using namespace sample_grader;
    h++;
    cout << "wait()";
    if (h <= H) {
        cout << " returns ";
        print_vector(answers);
    }
    cout << endl;

    if (h > H) wrong_answer("Out of time");

    vector<int> result = answers;
    answers.clear();
    return result;
}


int main()
{
    using namespace sample_grader;
    if (!(cin >> R >> H >> a >> b) || R <= 0 || H <= 0) invalid_input();
    if (a > b) swap(a, b);
    if (a < 1 or b > N) invalid_input();

    auto p = scout(R, H);
    cout << "scout(" << R << ", " << H << ") returned {" << p.first << ", " << p.second << "}" << endl;

    if (p.first > p.second) swap(p.first, p.second);

    if (p.first == a and p.second == b) {
        cout << "Correct: " << r << " robot(s) used, " << h << " hour(s) passed" << endl;
    } else {
        wrong_answer("Wrong answer");
    }
    return 0;
}

avoid.h: #include <cstdio>
#include <cstdlib>
#include <cassert>
#include <vector>
using namespace std;

namespace {
    constexpr int SEND = 114738923,
                  WAIT = 752019792,
                ANSWER = 539014118;
    constexpr size_t N = 1000;

    template<typename T> void write(T t) {
        fwrite(&t, sizeof(t), 1, stdout);
        fflush(stdout);
    }

    template<typename T> T read_or_exit() {
        T x;
        if(fread(&x, sizeof(x), 1, stdin) != 1) exit(0);
        return x;
    }

    int read_int_or_exit() {
        int x = read_or_exit<int>();
        if(x == -1) exit(0);
        return x;
    }

    void answer(pair<int, int> ans) {
        write(ANSWER); write(ans.first); write(ans.second);
    }
}

void send(vector<int> positions) {
    write(SEND);
    read_int_or_exit();

    if(positions.size() > N)
        write(-1), exit(0);
    write(static_cast<int>(positions.size()));

    vector<short> compressed; compressed.reserve(positions.size());
    for(int x : positions)
        compressed.push_back(static_cast<short>(x < -1 or x > 2000? -1 : x));

    if(fwrite(compressed.data(), sizeof(short), compressed.size(), stdout) != compressed.size())
        exit(0);
    fflush(stdout);
    read_int_or_exit();
}

vector<int> wait() {
    write(WAIT);

    int k = read_int_or_exit();
    vector<int> answers(k);
    if(fread(answers.data(), sizeof(int), answers.size(), stdin) != answers.size()) exit(0);
    return answers;
}

pair<int, int> scout(int, int);

int main() {
    int R = read_int_or_exit(), H = read_int_or_exit();
    answer(scout(R, H));
}

interactor.cpp: // Author: HeRaNO
// adapted from avoid/grader, testlib version
// #define DEBUG
#include "testlib.h"
#include<unordered_map>
#include<random>
#include<unordered_set>
#include<cassert>
using namespace std;

constexpr int N = 1000;

class adversary
{
 public:
    virtual ~adversary() {}

    virtual void send(vector<int>) = 0;
    virtual vector<int> wait() = 0;
    virtual bool answer(int, int) = 0;
};

class online_adversary : public adversary
{
 public:   
    void send(vector<int> locations)
    {
        replies.push_back(get_reply(locations));     
    }

    vector<int> wait()
    {
        vector<int> result = replies; replies.clear();
        return result;
    }

 protected:
    virtual int get_reply(vector<int>) = 0;
    
 private:
    vector<int> replies;
};

class offline_adversary : public adversary
{
 public:   
    void send(vector<int> locations)
    {
        queries.push_back(locations);
    }

    vector<int> wait()
    {
        vector<int> result = get_replies(queries);

        assert(result.size() == queries.size());

        queries.clear();
        return result;
    }

 protected:
    virtual vector<int> get_replies(vector<vector<int>>) = 0;
    
 private:
    vector<vector<int>> queries;
};

class fixed_adversary : public online_adversary
{
 public:
    fixed_adversary(int _a, int _b) : a(_a), b(_b)
    {
        if(a > b) swap(a, b);
    }

    bool answer(int x, int y)
    {
        if(x > y) swap(x, y);
        return x == a and y == b;   
    }

 protected:
    int get_reply(vector<int> locations)
    {
        for(int x : locations)
            if(x == a or x == b)
                return 1;    

        return 0;
    }
    
 private:
    int a, b;
};

class greedy_adversary : public offline_adversary
{
 public:
    greedy_adversary(int s) : outcomes(N + 1, 0), actual_outcome(0),
                              mask(1), reply_mask(1)
    {
        rnd_engine.seed(s);
    }

    bool answer(int x, int y)
    {
        if(x < y) swap(x, y);
    
        for(int a = 1; a <= N; ++a)
        {
            for(int b = 1; b <=a; ++b)
            {
                bitstring curr_outcome = outcomes[a] | outcomes[b];

                if(curr_outcome == actual_outcome and (a != x or b != y))
                {
                    #ifdef DEBUG
                        fprintf(stderr, "[selecting %d,%d instead of %d,%d]", 
                                a, b, x, y);
                    #endif

                    return false;
                }
            }
        }
        
        return true;
    }

    typedef __int128 bitstring;
    
 protected:
    vector<int> get_replies(vector<vector<int>> queries)
    {
        bitstring cutoff = mask - 1;
        
        update_outcomes(queries);

        unordered_map<bitstring, int> block_size;
        int max_block_size = 0;

        for(int x = 1; x <= N; ++x)
        {
            for(int y = 1; y <= x; ++y)
            {
                bitstring curr_outcome = outcomes[x] | outcomes[y];
                
                if((curr_outcome & cutoff) != actual_outcome)
                    continue;
            
                ++block_size[curr_outcome];
                max_block_size = max(max_block_size, block_size[curr_outcome]);
            }
        }

        vector<bitstring> possible_outcomes;
        for(auto b : block_size)
            if(b.second == max_block_size)
                possible_outcomes.push_back(b.first);
        assert(possible_outcomes.size() > 0);

        uniform_int_distribution<int> distr(0, possible_outcomes.size() - 1);
        actual_outcome = possible_outcomes[distr(rnd_engine)];

        #ifdef DEBUG
            fprintf(stderr, "[block size %d]", block_size[actual_outcome]);
        #endif

        return reply_from_bitstring(actual_outcome, queries.size());
    }

 private:
    vector<bitstring> outcomes;
    bitstring actual_outcome;
    
    bitstring mask;
    bitstring reply_mask;    
    
    mt19937 rnd_engine;

    // The following two functions must each be called exactly once in in
    // get_replies and in this order!
    void update_outcomes(vector<vector<int>> queries)
    {
        for(int i = 0; i < (int) queries.size(); ++i)
        {
            for(int x : queries[i])
                outcomes[x] += mask;
            mask <<= 1;
        }
    }
        
    vector<int> reply_from_bitstring(bitstring s, int length)
    {
        vector<int> reply;
    
        for(int i = 0; i < length; ++i)
        {
            reply.push_back(s & reply_mask ? 1 : 0);
            reply_mask <<= 1;
        }
        
        return reply;
    }

};

class single_adversary : public offline_adversary
{
  typedef __int128 bitstring;
 public:
    single_adversary(int s) : outcomes(N + 1, 0)
    {
        rnd_engine.seed(s);
    }

    bool answer(int x, int y)
    {
        if(x != y) return false;
    
        for(int a = 1; a <= N; ++a)
        {
            bitstring curr_outcome = outcomes[a];

            if(curr_outcome == actual_outcome and a != x)
            {
                #ifdef DEBUG
                    fprintf(stderr, "[selecting %d instead of %d]", a, x);
                #endif

                return false;
            }
        }
        
        return true;
    }
    
 protected:
    vector<int> get_replies(vector<vector<int>> queries)
    {
        bitstring mask = 1;
        
        for(int i = 0; i < (int) queries.size(); ++i)
        {
            for(int x : queries[i])
                outcomes[x] += mask;
            mask <<= 1;
        }

        unordered_set<bitstring> results;

        for(int x = 1; x <= N; ++x)
        {
            bitstring curr_outcome = outcomes[x];
            
            if(results.find(curr_outcome) == results.end())
            {
                results.insert(curr_outcome);
            }
            
            else
            {
                // We could just decide to not accept the answer at this
                // point -- however, we will instead actually find a
                // different possible set of locations in answer (this might
                // be helpful for debugging purposes)
                actual_outcome = curr_outcome;
                return reply_from_bitstring(actual_outcome, queries.size());
            }
        }

        uniform_int_distribution<int> dis(1, 1000);        
        actual_outcome = outcomes[dis(rnd_engine)];
        return reply_from_bitstring(actual_outcome, queries.size());
    }

 private:
    vector<bitstring> outcomes;
    bitstring actual_outcome;

    mt19937 rnd_engine;

    vector<int> reply_from_bitstring(bitstring s, int length)
    {
        vector<int> reply;
        bitstring mask = 1;
    
        for(int i = 0; i < length; ++i)
        {
            reply.push_back(s & mask ? 1 : 0);
            mask <<= 1;
        }
        
        return reply;
    }
};

class two_phase_adversary : public offline_adversary
{
 public:
    two_phase_adversary(int s) : outcomes(N + 1, 0), actual_outcome(0),
                                 mask(1), reply_mask(1), first_run(true)
    {
        rnd_engine.seed(s);
    }

    bool answer(int x, int y)
    {
        if(x < y) swap(x, y);
    
        for(int a = 1; a <= N; ++a)
        {
            for(int b = 1; b <=a; ++b)
            {
                bitstring curr_outcome = outcomes[a] | outcomes[b];

                if(curr_outcome == actual_outcome and (a != x or b != y))
                {
                    #ifdef DEBUG
                        fprintf(stderr, "[selecting %d,%d instead of %d,%d]", 
                                a, b, x, y);
                    #endif

                    return false;
                }
            }
        }
        
        return true;
    }

    typedef __int128 bitstring;
    typedef unordered_map<bitstring, int> block_map;
    
 protected:
    mt19937 rnd_engine;
    vector<bitstring> outcomes;

    vector<int> get_replies(vector<vector<int>> queries)
    {
        bitstring cutoff = mask - 1;
        
        update_outcomes(queries);

        block_map block_size;

        for(int x = 1; x <= N; ++x)
        {
            for(int y = 1; y <= x; ++y)
            {
                bitstring curr_outcome = outcomes[x] | outcomes[y];
                
                if((curr_outcome & cutoff) != actual_outcome)
                    continue;
            
                ++block_size[curr_outcome];
            }
        }

        if(first_run) actual_outcome = first_reply(block_size, queries);
        else          actual_outcome = second_reply(block_size, cutoff);

        first_run = false;

        return reply_from_bitstring(actual_outcome, queries.size());
    }

    virtual bitstring first_reply(const block_map&, vector<vector<int>>) = 0; // to be defined in subclass
    
    virtual bitstring second_reply(const block_map& block_size, bitstring cutoff)
    {
        vector<bitstring> possible_outcomes;

        for(auto b : block_size)
        {
            if((b.first & cutoff) != actual_outcome)
                continue;

            possible_outcomes.push_back(b.first);
        
            if(b.second > 1)
            {
                #ifdef DEBUG
                    fprintf(stderr, "[block size %d]", b.second);
                #endif
                
                return b.first;
            }
        }       

        assert(not possible_outcomes.empty());

        uniform_int_distribution<int> distr(0, possible_outcomes.size() - 1);
        return possible_outcomes[distr(rnd_engine)];
    }

 private:
    bitstring actual_outcome;
    
    bitstring mask;
    bitstring reply_mask;
    
    bool first_run;  

    // The following two functions must each be called exactly once in in
    // get_replies and in this order!
    void update_outcomes(vector<vector<int>> queries)
    {
        for(int i = 0; i < (int) queries.size(); ++i)
        {
            for(int x : queries[i])
                outcomes[x] += mask;
            mask <<= 1;
        }
    }
        
    vector<int> reply_from_bitstring(bitstring s, int length)
    {
        vector<int> reply;
    
        for(int i = 0; i < length; ++i)
        {
            reply.push_back(s & reply_mask ? 1 : 0);
            reply_mask <<= 1;
        }
        
        return reply;
    }

};


class preference_adversary : public two_phase_adversary
{
 public:
    preference_adversary(int preference, int s) : two_phase_adversary(s), preference(preference)
    {}

 protected:
    bitstring first_reply(const block_map& block_size, vector<vector<int>> _)
    {
        int best = -1;    
        for(auto b : block_size) best = max(best, value(b.first));

        vector<int> possible_outcomes;
        for(auto b : block_size)
            if(value(b.first) == best)
                possible_outcomes.push_back(b.first);

        assert(not possible_outcomes.empty());

        uniform_int_distribution<int> distr(0, possible_outcomes.size() - 1);
        bitstring curr_outcome = possible_outcomes[distr(rnd_engine)];

        #ifdef DEBUG
            fprintf(stderr, "[outcome %x for first run]", curr_outcome);
        #endif

        return curr_outcome;
    }

 private:
    int preference;

    int value(bitstring b)
    {
        bitstring mask = 1;
        int r = 0;

        while(mask)
        {
            if((bool)(b & mask) == (bool)(preference))
                ++r;
            mask <<= 1;
        }
        
        return r;
    }
};

class rnd_adversary : public two_phase_adversary
{
 public:
    rnd_adversary(int s) : two_phase_adversary(s)
    {}

 protected:
    bitstring first_reply(const block_map& block_size, vector<vector<int>> _)
    {
        vector<bitstring> possible_outcomes;
    
        for(auto b : block_size)
            possible_outcomes.push_back(b.first);

        assert(not possible_outcomes.empty());

        uniform_int_distribution<int> distr(0, possible_outcomes.size() - 1);
        bitstring curr_outcome = possible_outcomes[distr(rnd_engine)];

        #ifdef DEBUG
            fprintf(stderr, "[outcome %x for first run]", curr_outcome);
        #endif

        return curr_outcome;
    }
};

class xor_adversary : public two_phase_adversary
{
 public:
    xor_adversary(int preference, int s) : two_phase_adversary(s), preference(preference)
    {}

 protected:
    bitstring first_reply(const block_map& block_size, vector<vector<int>> q)
    {
        int l = q.size();
    
        unordered_map<bitstring, long long> total_value;
        long long best = -1;
        
        for(int x = 1; x <= N; ++x)
        {        
            for(int y = 1; y <= x; ++y)
            {
                bitstring curr_outcome = outcomes[x] | outcomes[y];
                                
                total_value[curr_outcome] += value(outcomes[x], outcomes[y], l);
                best = max(best, total_value[curr_outcome]);
            }
        }

        #ifdef DEBUG
            fprintf(stderr, "[best total_value is %lld]", best);
        #endif

        vector<bitstring> possible_outcomes;
        for(auto b : total_value)
            if(b.second == best) possible_outcomes.push_back(b.first);

        assert(not possible_outcomes.empty());

        uniform_int_distribution<int> distr(0, possible_outcomes.size() - 1);
        bitstring curr_outcome = possible_outcomes[distr(rnd_engine)];

        #ifdef DEBUG
            fprintf(stderr, "[outcome %x for first run]", curr_outcome);
        #endif

        return curr_outcome;
    }

 private:
    int preference;

    long long value(bitstring a, bitstring b, int size)
    {
        bitstring delta = a ^ b;
        bitstring mask = 1;
        long long r = 0;

        for(int i = 0; i < size; ++i)
        {
            if((bool)(delta & mask) == (bool)(preference))
                ++r;
            mask <<= 1;
        }

        return r * r; // we square this to skew in favour of extreme values
    }
};

class multiple_phase_adversary : public offline_adversary
{
 public:
    multiple_phase_adversary(int s, int R, int H) : outcomes(N + 1, 0), actual_outcome(0),
                                 mask(1), reply_mask(1), R_left(R), H_left(H)
    {
        rnd_engine.seed(s);
    }

    bool answer(int x, int y)
    {
        if(x < y) swap(x, y);
    
        for(int a = 1; a <= N; ++a)
        {
            for(int b = 1; b <=a; ++b)
            {
                bitstring curr_outcome = outcomes[a] | outcomes[b];

                if(curr_outcome == actual_outcome and (a != x or b != y))
                {
                    #ifdef DEBUG
                        fprintf(stderr, "[selecting %d,%d instead of %d,%d]", 
                                a, b, x, y);
                    #endif

                    return false;
                }
            }
        }
        
        return true;
    }

    typedef __int128 bitstring;
    typedef unordered_map<bitstring, int> block_map;
    
 protected:
    mt19937 rnd_engine;
    vector<bitstring> outcomes;

    vector<int> get_replies(vector<vector<int>> queries)
    {
        R_left -= (int) queries.size();
        H_left--;
        bitstring cutoff = mask - 1;
        
        update_outcomes(queries);

        block_map block_size;

        for(int x = 1; x <= N; ++x)
        {
            for(int y = 1; y <= x; ++y)
            {
                bitstring curr_outcome = outcomes[x] | outcomes[y];
                
                if((curr_outcome & cutoff) != actual_outcome)
                    continue;
            
                ++block_size[curr_outcome];
            }
        }

        actual_outcome = get_reply(block_size, cutoff);

        return reply_from_bitstring(actual_outcome, queries.size());
    }

 private:
    bitstring actual_outcome;
    
    bitstring mask;
    bitstring reply_mask;

    int R_left, H_left;

    bitstring get_reply(const block_map& block_size, bitstring cutoff)
    {
        vector<bitstring> possible_outcomes;

        int maxSep = R_left <= 60 ? 1ll<<R_left : 1ll<<60;

        for(auto b : block_size)
        {
            if((b.first & cutoff) != actual_outcome)
                continue;

            possible_outcomes.push_back(b.first);
        
            if(b.second > maxSep)
            {
                #ifdef DEBUG
                    fprintf(stderr, "[block size %d]", b.second);
                #endif
                
                return b.first;
            }
        }       

        assert(not possible_outcomes.empty());

        uniform_int_distribution<int> distr(0, possible_outcomes.size() - 1);
        return possible_outcomes[distr(rnd_engine)];
    }
    
    // The following two functions must each be called exactly once in in
    // get_replies and in this order!
    void update_outcomes(vector<vector<int>> queries)
    {
        for(int i = 0; i < (int) queries.size(); ++i)
        {
            for(int x : queries[i])
                outcomes[x] += mask;
            mask <<= 1;
        }
    }
        
    vector<int> reply_from_bitstring(bitstring s, int length)
    {
        vector<int> reply;
    
        for(int i = 0; i < length; ++i)
        {
            reply.push_back(s & reply_mask ? 1 : 0);
            reply_mask <<= 1;
        }
        
        return reply;
    }

};

adversary* create_adversary()
{
    auto ri = []()
    {
      return inf.readInt();
    };

    // char buffer[128];
    // assert(fscanf(fin, "%s", buffer) == 1);
    // string type = buffer;
    string type = inf.readToken();

    if(type == "fixed")       { return new fixed_adversary(ri(), ri());                }
    else if(type == "greedy") { return new greedy_adversary(ri());                     }
    else if(type == "single") { return new single_adversary(ri());                     }
    else if(type == "prefer") { return new preference_adversary(ri(), ri());           }
    else if(type == "rnd")    { return new rnd_adversary(ri());                        }
    else if(type == "close")  { return new xor_adversary(0, ri());                     }
    else if(type == "diff")   { return new xor_adversary(1, ri());                     }
    else if(type == "multi")  { return new multiple_phase_adversary(ri(), ri(), ri()); }
    else                      { throw "invalid input";                                 }
}

constexpr int SEND = 114738923, WAIT = 752019792, ANSWER = 539014118;
double score[] = {1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 0.9333333333333333, 0.8666666666666667, 0.8, 0.7333333333333333, 0.6933333333333334, 0.6533333333333333, 0.6133333333333333, 0.5733333333333334, 0.5333333333333333, 0.5066666666666667, 0.48, 0.4533333333333333, 0.4266666666666667, 0.4, 0.38666666666666666, 0.37333333333333335, 0.36, 0.3466666666666667, 0.3333333333333333, 0.32, 0.30666666666666664, 0.29333333333333333, 0.28, 0.26666666666666666, 0.25333333333333335, 0.24, 0.22666666666666666, 0.21333333333333335, 0.2, 0.18666666666666668, 0.17333333333333334, 0.16, 0.14666666666666667, 0.13333333333333333, 0.13333333333333333, 0.13333333333333333, 0.13333333333333333, 0.13333333333333333, 0.13333333333333333, 0.13333333333333333, 0.13333333333333333, 0.13333333333333333, 0.13333333333333333, 0.13333333333333333, 0.13333333333333333, 0.13333333333333333, 0.13333333333333333, 0.13333333333333333, 0.13333333333333333};

#ifdef DEBUG
    #define OUT_OF_RAVENS "Out of ravens"
    #define OUT_OF_TIME "Out of time"
    #define INVALID_SEND "Invalid send"
    #define WRONG_ANSWER(x,y) "Wrong answer %d %d", x, y
    #define CORRECT(r,h) "Correct: %d raven(s) used, %d hour(s) passed", r, h
    #define SECURITY_VIOLATION "Security violation!"
#else
    #define OUT_OF_RAVENS "Not correct"
    #define OUT_OF_TIME "Not correct"
    #define INVALID_SEND "Not correct"
    #define WRONG_ANSWER(x,y) "Not correct"
    #define CORRECT(r,h) "Correct: %d robot(s) used, %d hour(s) passed", r, h
    #define SECURITY_VIOLATION "Security violation!"
#endif

int R, H;
int r = 0, h = 0;
int use_partial_scoring;

void result(double _, const char *msg, ...) {
    va_list args;
    va_start(args, msg);
    quitf(_wa, msg, args);
}

void result(vector<float> v_score, vector<string> verdict) {
    double score = v_score.back();
    if (score == 1.0) {
        quitf(_ok, "%s", verdict.back().c_str());
    } else {
        quitp(score * 100, "%s", verdict.back().c_str());
    }
}

adversary* adv;

template<typename T> void write(T t) {
  fwrite(&t, sizeof(t), 1, stdout);
  fflush(stdout);
}

template<typename T> T read_or_fail() {
  T x;
  if(fread(&x, sizeof(x), 1, stdin) != 1)
    result(0.0, SECURITY_VIOLATION);
  return x;
}

void handle_send() {
    ++r;
    if(r > R) result(0.0, OUT_OF_RAVENS);
    write(1); // This is fine

    int k = read_or_fail<int>();
    if(k < 0 || k > N) result(0.0, INVALID_SEND);

    vector<short> shortdests(k);
    if(fread(shortdests.data(), sizeof(short), k, stdin) != (size_t) k)
        result(0.0, SECURITY_VIOLATION);
    vector<char> is_dest(N + 1, false);

    vector<int> dests; dests.reserve(k);
    for(int x : shortdests) {
        if(x <= 0 or x > N or is_dest[x])
            result(0.0, INVALID_SEND);
        is_dest[x] = true;
        dests.push_back(x);
    }

    adv->send(dests);

    // Tell the user program that everything is fine
    write(1);
}

void handle_wait() {
    ++h;
    if(h > H) result(0.0, OUT_OF_TIME);

    vector<int> answers = adv->wait();

    write(static_cast<int>(answers.size()));
    if(fwrite(answers.data(), sizeof(int), answers.size(), stdout) != answers.size())
        result(0.0, SECURITY_VIOLATION);
    fflush(stdout);
}

void handle_answer() {
    int x = read_or_fail<int>(), y = read_or_fail<int>();

    #ifdef DEBUG
        fprintf(stderr, "(user answers %d,%d)", x, y);
    #endif

    if(1 <= x and x <= N and 1 <= y and y <= N and adv->answer(x, y)) {
        char buffer[1024]; sprintf(buffer, CORRECT(r,h));
        if (R == 75 && H == 1)
            result(vector<float>({1.0, (float) score[r]}), vector<string>({buffer, buffer}));
        else
            result(vector<float>({1.0, 1.0}), vector<string>({buffer, buffer}));
    }
    else
        result(0.0, WRONG_ANSWER(x, y));
}

void check() {
    // message_on_shutdown = true;

    // assert(fscanf(fin, "%d %d", &R, &H) == 2);
    R = inf.readInt();
    H = inf.readInt();
    write(R); write(H);

    adv = create_adversary();

    for(;;) {
        int type = read_or_fail<int>();

        switch(type) {
            case SEND:
                handle_send();
                break;

            case WAIT:
                handle_wait();
                break;

            case ANSWER:
                handle_answer();
                break;

            default:
                result(0.0, SECURITY_VIOLATION);
                break;
        }
    }
}

int main(int argc, char *argv[]) {
    registerInteraction(argc, argv);
    check();
    return 0;
}