제출 #1298312

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1298312		tuandq	메시지 (IOI24_message)	C++20	45.75 / 100	482 ms	832 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) {
    // SEND C WITH OPTIMIZATIONS
    int ma = 0, pos = -1 ;
    for(int i = 0; i < 31; i ++) if(!C[i]) {
        int j = i ;
        while(j < 30 && !C[j + 1]) ++ j ;
        if(j - i + 1 > ma) {
            ma = j - i + 1 ; pos = i ;
        }
        i = j ;
    }
    
    if(ma == 1) {
        vector<vector<bool>> buck = encode(31, 5) ;
        for(vector<bool> &cur : buck) {
            send_packet(cur) ;
        }
    }
    
    else {
        vector<vector<bool>> buck = encode(pos, 5) ;
        for(vector<bool> &cur : buck) {
            send_packet(cur) ;
        }
        
        for(int i = 0; i < 31; i ++) {
            while(i >= pos && i < pos + 2) ++ i ;
            
            int j = i + 1 ;
            while(j >= pos && j < pos + 2) ++ j ;

            if(j >= 31) break ;
            
            vector<bool> pack(31, false) ;
            pack[pos] = C[i] ; pack[pos + 1] = C[j] ;
            send_packet(pack) ;

            // cerr << i << ' ' << j << endl ;
            
            i = j ;
        }
    }
    
    // SEND MESSAGE STRAIGHTLY FOWARD
    vector<int> idx ;
    for(int i = 0; i < 31; i ++) {
        if(!C[i]) idx.emplace_back(i) ;
    }

    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()) ;

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

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

        send_packet(pack) ;
    }
}

vector<bool> receive_message(vector<vector<bool>> R) {
    // DECODE THE STRING C    
    int pos = 0 ;
    for(int i = 0; i < 5; 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])) ;
    }
    
    int num = 5 ;
    vector<int> idx ;
    if(pos == 31) {
        for(int d = 0; d < 31; d += 2) {
            idx.emplace_back(d) ;
        }
    }
    else {
        num = 19 ;
        int cur = -1 ;
        idx.emplace_back(pos) ;
        idx.emplace_back(pos + 1) ;
        for(int i = 0; i < 14; i ++) {
            for(int x : {pos, pos + 1}) {
                ++ cur ;
                while(cur >= pos && cur < pos + 2) ++ cur ;
                if(!R[i + 5][x]) idx.emplace_back(cur) ; 
            }
        }
        if(idx.size() < 16) {
            ++ cur ;
            while(cur >= pos && cur < pos + 2) ++ cur ;
            idx.emplace_back(cur) ;
        }
        sort(idx.begin(), idx.end()) ;
    }
    // cerr << "Finished decoding C\n" ;
    
    // DECODE THE SIZE OF MESSAGE AND ITS BITS
    
    int numSz = 0 ;
    for(int i = 0; i < 10; i ++) {
        numSz = numSz << 1 | ((int)R[num][idx[i]]) ;
    }
    ++ numSz ;
    
    int iter = 9 ;
    vector<bool> res ;
    for(; numSz > 0; numSz --) {
        if(++ iter == 16) iter = 0, ++ num ;
        res.emplace_back(R[num][idx[iter]]) ;
    }
    return res ;
}

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