Submission #1099018

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099018		crafticat	Flight to the Ford (BOI22_communication)	C++17	0 / 100	14 ms	332 KiB

communication

#include <bits/stdc++.h>

using namespace std;
#define F0R(i, n) for (int i= 0; i < n;i++)
template<typename T>
using V = vector<T>;
using vi = V<int>;

int send(int bit);

int receive();
constexpr int TRIES = 10;

void sendBit(int x) {
    int next = 1;
    F0R(i, TRIES) {
        if (send(x)== x) {
            send(1);
        } else {
            send(next);
            next = !next;
        }
    }
}
int recBit() {
    map<int, int> target;
    int ans = -1;

    F0R(i, TRIES) {
        int x = receive();
        int y = receive();
        if (target.count(x) && target[x] != y && ans == -1) {
            ans = !x;
        }
        target[x] = y;
    }
    if (ans == -1 && target.size() == 1)
        ans = target.begin()->first;

    if (ans == -1)
        exit(5);
    return ans;
}

void encode(int n, int x) {
    srand(time(nullptr));

    int bits = log2(n + 1) + 1;
    F0R(i, bits) {
        sendBit(x % 2);
        x /= 2;
    }
}

std::pair<int, int> decode(int n) {
    int x = 0;
    int bits = log2(n + 1) + 1;
    int mul = 1;

    F0R(i, bits) {
        x += mul * recBit();
        mul *= 2;
    }

    return {x, n};
}

#if DEBUG

using namespace std;

void __attribute__((noreturn)) __attribute__((format(printf, 1, 2))) result(const char *msg, ...)
{
    va_list args;
    va_start(args, msg);
    vfprintf(stdout, msg, args);
    fprintf(stdout, "\n");
    va_end(args);
    exit(0);
}

namespace
{
    enum { ENCODE, DECODE } current_phase;
    int N, X;
    vector<int> signals;
    size_t cursor = 0;
    bool flipped = false;
}

int send(int s)
{
    if(current_phase == DECODE or (s != 0 and s != 1))
        result("Invalid send.");

    printf("send(%d) -> ", s); fflush(stdout);
    int answer = flipped ? s : !s;

    bool flipped_now = (s != answer);
    if(flipped and flipped_now)
        result("Invalid reply to send");
    flipped = flipped_now;

    signals.push_back(answer);
    if(signals.size() > (size_t) 250)
        result("Looks (and smells) fishy.");
    return signals.back();
}

int receive()
{
    if(current_phase == ENCODE)  result("Invalid receive.");
    if(cursor >= signals.size()) result("Assistant waiting for Godot.");
    int r = signals[cursor++];
    printf("receive() -> %d\n", r);
    return r;
}

int main()
{
    if(scanf("%d %d", &N, &X) != 2 or X < 1 or X > N)
        result("Invalid input.");

    current_phase = ENCODE;
    encode(N, X);
    current_phase = DECODE;
    auto r = decode(N);

    if(r.first < 1 or r.first > N or r.second < 1 or r.second > N)
        result("Invalid answer.");

    if(r.first == X or r.second == X)
        result("Correct: %d signals sent.", (int) signals.size());
    else
        result("Wrong answer.");
}
#endif

• Subtask 1: 0 / 15
• Subtask 2: 0 / 85