Submission #584055

#	Time	Username	Problem	Language	Result	Execution time	Memory
584055		cheissmart	Flight to the Ford (BOI22_communication)	C++17	74 / 100	3496 ms	2128 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, 0b1111};

vi get_bad(int x) {
    vi ans;
    for(int k = 0; k < 4; 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 < 4; 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 < 4; k++)
                if(z == aux[k])
                    ans.PB(k);
        }
    }
    vi bad;
    for(int i = 0; i < 4; i++)
        if(count(ALL(ans), i) == 0)
            bad.PB(i);
    return bad;
};

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

        return get_bad(sent);
    };
    function<void(int)> go = [&] (int m) { // [0, m);
        assert(x < m);
        if(m <= 4) {
            send_4(x);
            return;
        }
        int b = m / 2, a = b / 2, c = (b + m) / 2;
        int aux[] = {0, a, b, c, m};
        int which = 0;
        while(!(aux[which] <= x && x < aux[which + 1]))
            which++;
        vi bad = send_4(which);
        int new_m = m, new_x = x;

        for(int i = 0; i < 4; i++) {
            if(count(ALL(bad), i)) {
                new_m -= aux[i + 1] - aux[i];
                if(aux[i] < x) new_x -= aux[i + 1] - aux[i];
            }
        }

        x = new_x;
        go(new_m);
    };
    go(n);
}

pi decode(int n) {
    auto get_4 = [&] () {
        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 <= 4) {
            vi bad = get_4(), good;
            for(int i = 0; i < m; i++)
                if(count(ALL(bad), i) == 0)
                    good.PB(i);
            while(SZ(good) < 2)
                good.PB(0);
            return {good[0], good[1]};
        }
        vi bad = get_4();
        int b = m / 2, a = b / 2, c = (b + m) / 2;
        int aux[] = {0, a, b, c, m}, new_m = m;
        for(int i = 0; i < 4; i++) {
            if(count(ALL(bad), i)) {
                new_m -= aux[i + 1] - aux[i];
            }
        }
        auto go_back = [&] (int x) -> int {
            for(int i = 0; i < 4; i++) {
                if(count(ALL(bad), i)) {
                    x += aux[i + 1] - aux[i];
                } else {
                    if(aux[i] <= x && x < aux[i + 1])
                        return x;
                }
            }
            throw;
        };
        auto[x, y] = go(new_m);
        return {go_back(x), go_back(y)};
    };
    auto[x, y] = go(n);
    return {x + 1, y + 1};
}

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