Submission #1296616

#	Time	Username	Problem	Language	Result	Execution time	Memory
1296616		NotLinux	Message (IOI24_message)	C++20	83.31 / 100	447 ms	820 KiB

message

#include "message.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
#define all(x) x.begin() , x.end()
// send_packet(A);
int perm[31] = {28,23,16,0,2,10,7,18,11,14,9,27,19,17,15,4,12,24,3,21,6,30,1,25,5,26,29,8,20,22,13};
void send_message(vector<bool> M, vector<bool> C) {
    int mlen = sz(M);
    for(int i = 10;i>=0;i--){
        M.insert(M.begin() , mlen & (1 << i));
    }

    vector<bool> A(31, 1);// use this vector
    vector<int>released;// indexes in this vector will start sending the message
    // 1 : find a safe bit
    int msgsayac = 0;
    int PACKET = 0;
    function<int(int,int)> search = [&](int l , int r){
        if(l == r)return l;
        int mid = (l + r) / 2;// <= mid , > mid
        int cnt = 0;
        for(int i = l;i<=mid;i++)cnt += C[perm[i]] == 0;
        if(2 * cnt > (mid - l + 1)){
            for(int i = l;i<=r;i++)A[perm[i]] = 0;

            for(auto itr : released){
                if(msgsayac == sz(M))break;
                A[perm[itr]] = M[msgsayac++];
            }
            PACKET++;
            send_packet(A);

            for(int i = mid+1;i<=r;i++)if(C[perm[i]] == 0)released.push_back(i);
            sort(all(released));

            return search(l , mid);
        }
        else{
            for(int i = l;i<=r;i++)A[perm[i]] = 1;
            
            for(auto itr : released){
                if(msgsayac == sz(M))break;
                A[perm[itr]] = M[msgsayac++];
            }
            PACKET++;
            send_packet(A);

            for(int i = l;i<=mid;i++)if(C[perm[i]] == 0)released.push_back(i);
            sort(all(released));

            return search(mid+1 , r);
        }
    };
    int safebit = search(0,30);
    // cerr << "1 safe bit : " << safebit << endl;
    // 2 : show all
    for(int i = 0;i<31;i++){
        if(i == safebit)continue;
        A[perm[safebit]] = C[perm[i]];
        // cerr << PACKET << " sent : " << i << " = " << C[i] << endl;
        for(auto itr : released){
            if(msgsayac == sz(M))break;
            A[perm[itr]] = M[msgsayac++];
        }
        PACKET++;
        send_packet(A);
    }
    released.push_back(safebit);
    sort(all(released));
    // 3 : finish the message
    while(msgsayac < sz(M)){
        for(auto itr : released){
            if(msgsayac == sz(M))break;
            A[perm[itr]] = M[msgsayac++];
        }
        send_packet(A);
    }
}

vector<bool> receive_message(vector<vector<bool>> R) {
    int mlen = 0 , lensayac = 0;

    vector<bool>M;
    int state = 0;
    int l = 0 , r = 30 , safebit = -1 , cur = 0 , crit[31] , indx = 0;
    memset(crit , -1 , sizeof(crit));
    vector<int>vsafe;
    int PACKET = 0;
    for(auto packet : R){
        if(state == 0){
            int mid = (l + r) / 2;
            int cnt = 0;
            for(int i = l;i<=r;i++){
                cnt += packet[perm[i]] == 0;
            }
            if(2 * cnt > (r - l + 1)){// sola
                for(int i = mid+1;i<=r;i++)crit[perm[i]] = indx+1;
                r = mid;
            }
            else{
                for(int i = l;i<=mid;i++)crit[perm[i]] = indx+1;
                l = mid+1;
            }
            if(l == r){
                safebit = l;
                vsafe.push_back(safebit);
                state = 1;
            }
        }
        else if(state == 1){
            if(cur == safebit)cur++;

            if(packet[perm[safebit]] == 0){
                // cout << "BRUH : " << PACKET << " " << cur << endl;
                vsafe.push_back(cur);
            }
            cur++;
            if(cur == safebit)cur++;
            if(cur == 31){
                state = 2;
                crit[perm[safebit]] = indx+1;
            }
        }
        indx++;
        PACKET++;
    }
    // cerr << "2 safe bit : " << safebit << endl;
    sort(all(vsafe));
    // cerr << "vsafe : ";for(auto itr : vsafe)cout << itr << " ";cout << endl;
    for(int i = 0;i<sz(R);i++){
        for(auto itr : vsafe){
            if(i < crit[perm[itr]])continue;
            if(lensayac <= 10){
                mlen += R[i][perm[itr]] * (1 << lensayac);
                lensayac++;
            }
            else{
                M.push_back(R[i][perm[itr]]);
            }
        }
    }
    // cout << "mlen : " << mlen << endl;
    while(sz(M) > mlen)M.pop_back();
    return M;
}

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