제출 #1298467

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1298467		tuandq	메시지 (IOI24_message)	C++20	79.64 / 100	414 ms	828 KiB

message

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

vector<bool> send_packet(vector<bool> A);

vector<vector<bool>> encode(int num, const int &d) {
    vector<vector<bool>> res ;
    for(int i = d - 1; i > -1; i --) {
        res.emplace_back(vector<bool>(31, (bool)(num >> i & 1))) ;
    }
    return res ;
}

void send_message(vector<bool> M, vector<bool> C) {
    vector<int> idx ;
    for(int i = 0; i < 31; i ++) {
        if(!C[i]) idx.emplace_back(i) ;
    }
    vector<vector<bool>> buck = encode(idx[0], 4) ;
    for(vector<bool> &cur : buck) send_packet(cur) ;

    int s = (int)M.size() - 1 ;
    reverse(M.begin(), M.end()) ;
    for(int i = 0; i < 10; i ++) {
        M.emplace_back((bool)(s >> i & 1)) ;
    }
    reverse(M.begin(), M.end()) ;

    int cnt = 0 ;
    for(int i = 0; i < M.size() || cnt < 29;) {
        vector<bool> pack(31, false) ;

        int x = min((int)M.size() - i + (cnt < 29), 16) ;
        for(int j = cnt < 29; j < x; j ++) {
            pack[idx[j]] = M[i] ; ++ i ;
        }
        if(cnt < 29) pack[idx[0]] = C[cnt + (cnt >= idx[0])] ;

        // for(bool cur : pack) cerr << i << ' ' << cur << endl ;
        // cerr << endl ;

        send_packet(pack) ; ++ cnt ;
    }
}

vector<bool> receive_message(vector<vector<bool>> R) {
    int pos = 0 ;
    for(int i = 0; i < 4; i ++) {
        vector<int> cnt(2, 0) ;
        for(int j = 0; j < 31; j ++) {
            ++ cnt[(int)R[i][j]] ;
        }
        pos = pos << 1 | ((int)(cnt[1] > cnt[0])) ;
    }
    // cerr << "Found " << pos << endl ;

    vector<int> idx ; idx.emplace_back(pos) ;
 
    int cnt = 0, cur = 0 ;
    for(int i = 0; i < 29; i ++, cur ++) {
        if(cur == pos) ++ cur ;
        if(!R[i + 4][pos]) -- cnt, idx.emplace_back(cur) ;
        else ++ cnt ;

        // cerr << cur << ' ' << R[i + 4][pos] << endl ;
    }
    if(cnt > 0) idx.emplace_back(cur += (cur == pos)) ;

    // for(int x : idx) cerr << x << ' ' ;
    // cerr << endl ;

    // cerr << "Finished decoding C" << endl ;

    int numSz = 0 ;
    for(int i = 1; i < 11; i ++) {
        numSz = numSz << 1 | ((int)R[4][idx[i]]) ;
    }
    ++ numSz ;

    cerr << "Size equals " << numSz << endl ;
    
    vector<bool> res ;
    int iter = 10, num = 4 ; cnt = 0 ;
    for(; numSz > 0; numSz --) {
        if(++ iter == 16) iter = (++ cnt < 29), ++ num ;
        res.emplace_back(R[num][idx[iter]]) ;
    }
    return res ;
}

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