Submission #1104402

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104402		fve5	Flight to the Ford (BOI22_communication)	C++17	72 / 100	3928 ms	3076 KiB

communication

#include <bits/stdc++.h>
#include "communication.h"
using namespace std;

constexpr int MAXBITS = 30;
constexpr int LEN = 118;

int change_index_extremes_equal(int idx) {
    switch (idx) {
    case 0: return 0;
    case 1: return 0;
    case 2: return 1;
    case 3: return 2;
    case 4: return 1;
    case 5: return 2;
    case 6: return 3;
    case 7: return 3;
    }
}

vector<int> change_from_idx_eq(int idx, bool preserve) {
    if (preserve) {
        switch (idx) {
        case 0: return {0, 0, 0, 0};
        case 1: return {0, 1, 0, 0};
        case 2: return {0, 0, 1, 0};
        case 3: return {1, 0, 0, 1};
        }
    } else {
        switch (idx) {
        case 0: return {1, 0, 0, 0};
        case 1: return {1, 0, 1, 0};
        case 2: return {0, 0, 0, 1};
        case 3: return {0, 1, 0, 1};
        }
    }
}

int idx_from_change(int sz, vector<int> ch) {
    int cnt = 0;

    for (int i = 0; i < (1 << sz); i++) {
        bool ok = true;
        for (int j = 0; j < sz; j++)
            ok &= (i >> j) % 4 != 3;
        
        if (!ok)
            continue;

        bool match = true;
        for (int j = 0; j < sz; j++)
            match &= ch[j] == (i >> j) % 2;

        if (match)
            return cnt;

        cnt++;
    }
}

vector<int> change_from_idx(int sz, int idx) {
    int cnt = 0;
    vector<int> ans(sz);

    for (int i = 0; i < (1 << sz); i++) {
        bool ok = true;
        for (int j = 0; j < sz; j++)
            ok &= (i >> j) % 4 != 3;
        
        if (!ok)
            continue;

        if (cnt == idx) {
            for (int j = 0; j < sz; j++)
                ans[j] = (i >> j) % 2;
            return ans;
        }

        cnt++;
    }
}

int send_packet(int sz, vector<int> b) {
    vector<int> ch(sz);
    for (int i = 0; i < sz; i++) {
        ch[i] = b[i] ^ send(b[i]);
    }
    return idx_from_change(sz, ch);
}

void encode(int N, int X) {
    X--;
    vector<int> bits(MAXBITS);
    for (int i = 0; i < MAXBITS; i++)
        bits[i] = (X >> i) & 1;
    
    // Sending message
    int last = send_packet(4, {bits[0], bits[1], bits[2], bits[3]});
    for (int i = 4; i < MAXBITS; i++) {
        last = send_packet(4, {bits[i], (last >> 0) & 1, (last >> 1) & 1, (last >> 2) & 1});
    }

    // 8 states from 4
    last = send_packet(4, {(last >> 0) & 1, (last >> 1) & 1, (last >> 2) & 1, (last >> 0) & 1});
    last = change_index_extremes_equal(last);

    // 4 states from 3
    last = send_packet(2, {(last >> 0) & 1, (last >> 1) & 1});
    
    // Solution for N=3
    switch (last) {
    case 0: send_packet(4, {0, 0, 0, 0}); break;
    case 1: send_packet(4, {0, 1, 1, 0}); break;
    case 2: send_packet(4, {1, 0, 0, 1}); break;
    }
}

pair<int, int> starting_guesses(vector<int> packet) {
    int val = packet[0] | 2 * packet[1] | 4 * packet[2] | 8 * packet[3];
    switch (val) {
        case  0: return {0, 2};
        case  1: return {0, 2};
        case  2: return {0, 1};
        case  3: return {1, 2};
        case  4: return {0, 1};
        case  5: return {0, 0};
        case  6: return {1, 1};
        case  7: return {1, 1};
        case  8: return {0, 2};
        case  9: return {0, 2};
        case 10: return {0, 0};
        case 11: return {2, 2};
        case 12: return {1, 2};
        case 13: return {2, 2};
        case 14: return {1, 1};
        case 15: return {1, 1};
    }
}

int solve(int start, vector<int> packets) {
    int changed = start;

    auto pop = [&]() {
        int ans = packets.back();
        packets.pop_back();
        return ans;
    };

    // 3 states to 4
    {
        vector<int> packet = {pop(), pop()};
        vector<int> changes = change_from_idx(2, changed);
        reverse(changes.begin(), changes.end());

        changed = (changes[0] ^ packet[0]) * 2 | (changes[1] ^  packet[1]);
    }

    // 4 states to 8
    {
        vector<int> packet = {pop(), pop(), pop(), pop()};
        vector<int> changes = change_from_idx_eq(changed, packet[0] == packet[3]);
        reverse(changes.begin(), changes.end());

        changed = (changes[1] ^ packet[1]) * 4 | (changes[2] ^  packet[2]) * 2 | (changes[3] ^ packet[3]);
    }

    // 8 states to full message
    int ans = 0;

    while (!packets.empty()) {
        vector<int> packet = {pop(), pop(), pop(), pop()};
        vector<int> changes = change_from_idx(4, changed);
        reverse(changes.begin(), changes.end());

        if (!packets.empty()) {
            changed = (changes[0] ^ packet[0]) * 4 | (changes[1] ^  packet[1]) * 2 | (changes[2] ^ packet[2]);

            ans <<= 1;
            ans |= changes[3] ^ packet[3];
        } else {
            for (auto i: {0, 1, 2, 3}) {
                ans <<= 1;
                ans |= changes[i] ^ packet[i];  
            }
        }
    }
    return ans;
}

pair<int, int> decode(int N) {
    vector<int> packets(LEN);
    for (int i = 0; i < LEN; i++)
        packets[i] = receive();

    vector<int> head(packets.end() - 4, packets.end());
    vector<int> tail(packets.begin(), packets.end() - 4);

    auto [guess_1, guess_2] = starting_guesses(head);

    return {min(N, solve(guess_1, tail) + 1), min(N, solve(guess_2, tail) + 1)};
}

Compilation message (stderr)

communication.cpp: In function 'int change_index_extremes_equal(int)':
communication.cpp:19:1: warning: control reaches end of non-void function [-Wreturn-type]
   19 | }
      | ^
communication.cpp: In function 'std::vector<int> change_from_idx_eq(int, bool)':
communication.cpp:37:1: warning: control reaches end of non-void function [-Wreturn-type]
   37 | }
      | ^
communication.cpp: In function 'int idx_from_change(int, std::vector<int>)':
communication.cpp:59:1: warning: control reaches end of non-void function [-Wreturn-type]
   59 | }
      | ^
communication.cpp: In function 'std::vector<int> change_from_idx(int, int)':
communication.cpp:81:1: warning: control reaches end of non-void function [-Wreturn-type]
   81 | }
      | ^
communication.cpp: In function 'std::pair<int, int> starting_guesses(std::vector<int>)':
communication.cpp:138:1: warning: control reaches end of non-void function [-Wreturn-type]
  138 | }
      | ^

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