Submission #1246977

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246977		qwerasdfzxcl	Message (IOI24_message)	C++20	95.50 / 100	393 ms	872 KiB

message

#include "message.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

vector<vector<bool>> encode(vector<int> A, vector<bool> M){
    ll x = 0;
    for (int i=0;i<40;i++) if (M[i]) x |= 1LL<<i;

    ll fact[16];
    fact[0] = 1;
    for (int i=1;i<16;i++) fact[i] = fact[i-1] * i;

    assert(x < fact[15]);

    vector<int> used(15), P;
    for (int i=0;i<15;i++){
        for (int j=0;j<15;j++) if (!used[j]){
            if (x >= fact[14-i]){
                x -= fact[14-i];
                continue;
            }

            used[j] = 1;
            P.push_back(A[j]);
            break;
        }
    }

    P.push_back(A.back());
    P.insert(P.begin(), A.back());

    vector<vector<bool>> ret(5, vector<bool>(31));
    
    for (int i=0;i<(int)P.size()-1;i++){
        for (int j=0;j<5;j++){
            if (P[i+1] & (1<<j)) ret[j][P[i]] = true;
            else ret[j][P[i]] = false;
        }
    }

    return ret;
}

void send_message(std::vector<bool> M, std::vector<bool> C) {
    M.push_back(true);
    while(M.size() < 40 || M.size() % 16 != 8) M.push_back(false);

    vector<int> A;
    for (int i=0;i<31;i++) if (!C[i]) A.push_back(i);
    assert(A.size() == 16);

    auto ret = encode(A, vector<bool>(M.begin(), M.begin() + 40));
    for (auto &V:ret) send_packet(V);

    for (int i=40;i<(int)M.size();i+=16){
        vector<bool> V(31);
        for (int j=0;j<16;j++) V[A[j]] = M[i+j];
        send_packet(V);
    }
}

pair<vector<int>, vector<bool>> decode(vector<vector<bool>> R){
    vector<int> go(31);
    for (int i=0;i<5;i++){
        for (int j=0;j<31;j++){
            if (R[i][j]) go[j] |= 1<<i;
        }
    }

    for (int j=0;j<31;j++) if (go[j]==31) go[j] = 0;

    vector<int> P;
    for (int i=0;i<31;i++){
        P.clear();

        for (int j=i;;j=go[j]){
            if (find(P.begin(), P.end(), j) != P.end()) break;
            P.push_back(j);
        }

        if (P.end() - find(P.begin(), P.end(), go[P.back()]) != 16) continue;
        
        P.erase(P.begin(), find(P.begin(), P.end(), go[P.back()]));
        rotate(P.begin(), max_element(P.begin(), P.end()), P.end());
        rotate(P.begin(), P.begin()+1, P.end());

        break;
    }

    ll x = 0;
    
    ll fact[16];
    fact[0] = 1;
    for (int i=1;i<16;i++) fact[i] = fact[i-1] * i;

    vector<int> A = P, used(P.size());
    sort(A.begin(), A.end());

    for (int i=0;i<15;i++){
        for (int j=0;j<15;j++){
            if (P[i] == A[j]){
                used[j] = 1;
                break;
            }
            
            if (!used[j]) x += fact[14-i];
        }
    }

    vector<bool> M(40);
    for (int i=0;i<40;i++) if (x&(1LL<<i)) M[i] = true;

    return {A, M};
}

std::vector<bool> receive_message(std::vector<std::vector<bool>> R) {
    auto [A, M] = decode(vector<vector<bool>>(R.begin(), R.begin() + 5));

    for (int i=5;i<(int)R.size();i++){
        for (int j=0;j<16;j++){
            if (R[i][A[j]]) M.push_back(true);
            else M.push_back(false);
        } 
    }

    while(!M.back()) M.pop_back();
    M.pop_back();

    return M;
}

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