Submission #1198934

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198934		sqrtxsunlight	Message (IOI24_message)	C++20	91.23 / 100	452 ms	852 KiB

message

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

namespace Encode
{
    bool next_bit (vector <bool> &M)
    {
        if (M.size () == 0) return 0;
        bool res = M.back ();
        M.pop_back ();
        return res;
    }

    int first_4 (int l, int r, vector <bool> &M, vector <bool> &C)
    {
        if (l == r) return l;

        vector <int> ok_in, ok_out;
        for (int i = 0; i <= 30; i ++)
        {
            if (C[i] == 0)
            {
                if (l <= i and i <= r and ok_in.size () <= (r - l) / 2)
                    ok_in.push_back (i);
                else ok_out.push_back (i);
            }
        }

        int left_cnt = 0, right_cnt = 0;
        for (int i = l; i <= r; i ++)
        {
            if (C[i] == 0)
            {
                if (i - l < r - i) left_cnt ++;
                if (r - i < i - l) right_cnt ++;
            }
        }

        bool decide = (left_cnt < right_cnt);
        vector <bool> next_packet (31, 0);
        for (auto i: ok_out) next_packet[i] = next_bit (M);
        for (auto i: ok_in) next_packet[i] = decide;
        send_packet (next_packet);

        int next_group = (r - l) / 2;
        if (decide == false) return first_4 (l, l + next_group - 1, M, C);
        else return first_4 (r - next_group + 1, r, M, C);
    }

    void next_29 (int ok, vector <bool> &M, vector <bool> &C)
    {
        vector <bool> info;
        for (int i = 0; i < 31; i ++)
            if (i != ok and info.size () < 29)
                info.push_back (C[i]);
        reverse (info.begin (), info.end ());

        for (int i = 0; i < 29; i ++)
        {
            vector <bool> next_packet (31, 0);
            for (int j = 0; j < 31; j ++)
            {
                if (C[j] == 0)
                {
                    if (j != ok) next_packet[j] = next_bit (M);
                    else next_packet[j] = next_bit (info);
                }
            }

            send_packet (next_packet);
        }

        return;
    }

    void remaining (vector <bool> &M, vector <bool> &C)
    {
        if (M.size () == 0) return;

        vector <bool> next_packet (31, 0);
        for (int j = 0; j < 31; j ++)
            if (C[j] == 0)
                next_packet[j] = next_bit (M);

        send_packet (next_packet);
        return remaining (M, C);
    }

    void encode (vector <bool> M, vector <bool> C)
    {
        M.push_back (1);
        reverse (M.begin (), M.end ());
        int ok = first_4 (0, 30, M, C);
        next_29 (ok, M, C);
        remaining (M, C);
    }
}

void send_message (vector <bool> M, vector <bool> C)
{
    return Encode::encode (M, C);
}

namespace Decode
{
    int find_ok (int l, int r, int pos, vector <vector <bool>> &R)
    {
        if (l == r) return l;

        int vote = 0;
        for (int i = l; i <= r; i ++)
        {
            if (R[pos][i]) vote ++;
            else vote --;
        }

        int next_group = (r - l) / 2;
        if (vote < 0) return find_ok (l, l + next_group - 1, pos + 1, R);
        else return find_ok (r - next_group + 1, r, pos + 1, R);
    }

    vector <bool> read_C (int ok, vector <vector <bool>> &R)
    {
        vector <bool> C;
        int ok_count = 0;
        for (int i = 4; i < 4 + 29; i ++)
        {
            if (C.size () == ok) C.push_back (0);
            C.push_back (R[i][ok]);
            if (C.back () == 0) ok_count ++;
        }
        if (ok_count < 15) C.push_back (0);
        else C.push_back (1);

        return C;
    }

    vector <bool> read_first_4 (int l, int r, int pos, vector <vector <bool>> &R, vector <bool> &C)
    {
        if (l == r) return {};

        vector <int> ok_in, ok_out;

        for (int i = 0; i < 31; i ++)
        {
            if (C[i] == 0)
            {
                if (l <= i and i <= r and ok_in.size () <= (r - l) / 2)
                    ok_in.push_back (i);
                else ok_out.push_back (i);
            }
        }

        vector <bool> ans;
        for (auto i: ok_out) ans.push_back (R[pos][i]);

        vector <bool> next_ans;
        int next_group = (r - l) / 2;
        if (R[pos][ok_in[0]] == false) next_ans = read_first_4 (l, l + next_group - 1, pos + 1, R, C);
        else next_ans = read_first_4 (r - next_group + 1, r, pos + 1, R, C);

        for (auto i: next_ans) ans.push_back (i);
        return ans;
    }

    vector <bool> read_next_29 (int ok, vector <vector <bool>> &R, vector <bool> &C)
    {
        vector <bool> ans;

        for (int i = 4; i < 4 + 29; i ++)
        {
            for (int j = 0; j < 31; j ++)
            {
                if (j == ok) continue;
                if (C[j] == 0) ans.push_back (R[i][j]);
            }
        }

        return ans;
    }

    vector <bool> read_remaining (vector <vector <bool>> &R, vector <bool> &C)
    {
        vector <bool> ans;
        for (int i = 4 + 29; i < R.size (); i ++)
            for (int j = 0; j < 31; j ++)
                if (C[j] == 0)
                    ans.push_back (R[i][j]);

        return ans;
    }

    vector <bool> decode (vector <vector <bool>> R)
    {
        int ok = find_ok (0, 30, 0, R);

        vector <bool> C = read_C (ok, R);

        vector <bool> f4 = read_first_4 (0, 30, 0, R, C);
        vector <bool> n29 = read_next_29 (ok, R, C);
        vector <bool> remain = read_remaining (R, C);

        vector <bool> ans;
        for (auto i: f4) ans.push_back (i);
        for (auto i: n29) ans.push_back (i);
        for (auto i: remain) ans.push_back (i);

        while (ans.back () == 0) ans.pop_back ();
        ans.pop_back ();

        return ans;
    }
}

vector <bool> receive_message (vector <vector <bool>> R)
{
    return Decode::decode (R);
}

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 81.225 / 90