Submission #584042

#	Time	Username	Problem	Language	Result	Execution time	Memory
584042		cheissmart	Flight to the Ford (BOI22_communication)	C++17	30 / 100	5776 ms	2040 KiB

communication

#include"communication.h"
#include <bits/stdc++.h>
#define IO_OP ios::sync_with_stdio(0), cin.tie(0)
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7;

int aux[] = {0b0000, 0b1001, 0b0110};

int get_bad(int x) {
    vi ans;
    for(int k = 0; k < 3; k++)
        if(x == aux[k])
            ans.PB(k);
    for(int i = 0; i < 4; i++) {
        int y = x ^ (1 << i);
        for(int k = 0; k < 3; k++)
            if(y == aux[k])
                ans.PB(k);
        for(int j = 0; j < i - 1; j++) {
            int z = y ^ (1 << j);
            for(int k = 0; k < 3; k++)
                if(z == aux[k])
                    ans.PB(k);
        }
    }
    for(int i = 0; i < 3; i++)
        if(count(ALL(ans), i) == 0)
            return i;
    throw;
};

void encode(int n, int x) {
    x--;
    auto send_3 = [&] (int y) {
        assert(0 <= y && y < 3);
        int sent = 0;
        for(int i = 0; i < 4; i++)
            sent |= send(aux[y] >> i & 1) << i;

        #ifdef CHEISSMART
        assert(get_bad(sent) != y);
        #endif

        return get_bad(sent);
    };
    function<void(int)> go = [&] (int m) { // [0, m);
        assert(x < m);
        if(m <= 3) {
            send_3(x);
            return;
        }
        int he = m / 3, be = he * 2;
        // [0, he), [he, be), [be, m)
        if(x < he) {
            int bad = send_3(0);
            if(bad == 1) go(he + m - be);
            else if(bad == 2) go(be);
            else throw;
        } else if(x < be) {
            int bad = send_3(1);
            if(bad == 0) {
                x -= he;
                go(m - he);
            } else if(bad == 2) {
                go(be);
            } else throw;
        } else {
            int bad = send_3(2);
            if(bad == 0) {
                x -= he;
                go(m - he);
            } else if(bad == 1) {
                x -= be - he;
                go(he + m - be);
            } else throw;
        }
    };
    go(n);
}

pi decode(int n) {
    auto get_3 = [&] () {
        int x = 0;
        for(int i = 0; i < 4; i++)
            x |= receive() << i;
        return get_bad(x);
    };
    function<pi(int)> go = [&] (int m) -> pi { // [0, m);
        if(m <= 3) {
            int bad = get_3();
            if(bad == 0) return {1, 2};
            else if(bad == 1) return {0, 2};
            else return {0, 1};
        }
        int he = m / 3, be = he * 2;
        // [0, he), [he, be), [be, m)
        int bad = get_3();
        if(bad == 0) {
            auto [x, y] = go(m - he);
            x += he, y += he;
            return {x, y};
        } else if(bad == 1) {
            auto [x, y] = go(he + m - be);
            if(x >= he) x += be - he;
            if(y >= he) y += be - he;
            return {x, y};
        } else {
            auto [x, y] = go(be);
            return {x, y};
        }
    };
    auto[x, y] = go(n);
    return {x + 1, y + 1};
}

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