Submission #1296588

#	Time	Username	Problem	Language	Result	Execution time	Memory
1296588		NotLinux	Message (IOI24_message)	C++20	10 / 100	402 ms	808 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);

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));
    }
    // cout << "M : ";for(auto itr : M)cout << itr << " ";cout << endl;

    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;
    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[i] == 0;
        if(2 * cnt > (mid - l + 1)){
            for(int i = l;i<=r;i++)A[i] = 0;

            for(auto itr : released){
                if(msgsayac == sz(M))break;
                A[itr] = M[msgsayac++];
            }
            // cout << "released : ";for(auto itr : released)cout << itr << " ";cout << endl;
            // cout << "sent : ";for(auto itr : A)cout << itr << " ";cout << endl;
            send_packet(A);

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

            return search(l , mid);
        }
        else{
            for(int i = l;i<=r;i++)A[i] = 1;

            
            for(auto itr : released){
                if(msgsayac == sz(M))break;
                A[itr] = M[msgsayac++];
            }
            // cout << "released : ";for(auto itr : released)cout << itr << " ";cout << endl;
            // cout << "sent : ";for(auto itr : A)cout << itr << " ";cout << endl;
            send_packet(A);

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

            return search(mid+1 , r);
        }
    };
    int safebit = search(0,30);
    // 2 : show all
    for(int i = 0;i<31;i++){
        if(i == safebit)continue;
        A[safebit] = C[i];
        for(auto itr : released){
            if(msgsayac == sz(M))break;
            A[itr] = M[msgsayac++];
        }
        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[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;
    for(auto packet : R){
        if(state == 0){
            int mid = (l + r) / 2;
            int cnt = 0;
            for(int i = l;i<=r;i++){
                cnt += packet[i] == 0;
            }
            if(2 * cnt > (r - l + 1)){// sola
                for(int i = mid+1;i<=r;i++)crit[i] = indx+1;
                r = mid;
            }
            else{
                for(int i = l;i<=mid;i++)crit[i] = indx+1;
                l = mid+1;
            }
            if(l == r){
                safebit = l;
                state = 1;
            }
        }
        else if(state == 1){
            if(cur == safebit)cur++;
            if(packet[safebit] == 0){
                vsafe.push_back(cur);
            }
            cur++;
            if(cur == safebit)cur++;
            if(cur == 31){
                state = 2;
                crit[safebit] = indx+1;
            }
        }
        indx++;
    }
    // cout << "crit : ";for(int i = 0;i<31;i++)cout << crit[i] << " ";cout << endl;
    sort(all(vsafe));
    for(int i = 0;i<sz(R);i++){
        for(auto itr : vsafe){
            if(itr == safebit or i < crit[itr])continue;
            // cout << R[i][itr] << " ";
            if(lensayac <= 10){
                mlen += R[i][itr] * (1 << lensayac);
                lensayac++;
            }
            else{
                M.push_back(R[i][itr]);
            }
        }
    }
    while(sz(M) > mlen)M.pop_back();
    // cout << "mlen : " << mlen << endl;
    return M;
}

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