제출 #1129630

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1129630		c0det1ger	메시지 (IOI24_message)	C++20	56.20 / 100	631 ms	868 KiB

message

#include <bits/stdc++.h>
using namespace std;
 
//#define int long long
#define double long double

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

void send_message(vector<bool> M, vector<bool> C){
    int sz = (int)M.size();
    vector<int> blank;
    for (int i = 0; i < 31; i++){
        if (C[i] == 0){
            blank.push_back(i);
        }
    }
    int c1 = 0, c2 = 0;
    for (int i = 0; i < 16; i++){
        c1 += (1 - C[i]);
    }
    for (int i = 15; i < 31; i++){
        c2 += (1 - C[i]);
    }
    if (c2 > c1){
        vector<bool> send(31);
        for (int i = 0; i < 31; i ++){
            send[i] = 1;
        }
        send_packet(send);
        
        for (int i = 0; i < 9; i++){
            vector<bool> send(31);
            
            if (C[30 - i] == 1){
                for (int i = 1; i < 31; i += 2){
                    send[i] = 1;
                }
            }
            else{
                for (int i = 0; i < 31; i += 2){
                    send[i] = 1;
                }
            }
            send_packet(send);
        }
        int culm = 9;
        reverse(blank.begin(), blank.end());
        for (int i = 2; i < 16; i *= 2){
            vector<bool> send(31);
            
            for (int j = 0; j < i; j++){
                send[blank[j]] = C[30 - (culm + j)];
            }
            
            culm += i;
            
            send_packet(send);
        }
        vector<bool> snd(31);
        
        for (int j = 0; j < 8; j++){
            snd[blank[j]] = C[30 - (culm + j)];
        }
        
        send_packet(snd);
    }
    else{
        vector<bool> send(31);
        for (int i = 0; i < 31; i++){
            send[i] = 0;
        }
        send_packet(send);
        
        for (int i = 0; i < 9; i++){
            vector<bool> send(31);
            
            if (C[i] == 1){
                for (int i = 1; i < 31; i += 2){
                    send[i] = 1;
                }
            }
            else{
                for (int i = 0; i < 31; i += 2){
                    send[i] = 1;
                }
            }
            send_packet(send);
        }
        int culm = 9;
        for (int i = 2; i < 16; i *= 2){
            vector<bool> send(31);
            
            for (int j = 0; j < i; j++){
                send[blank[j]] = C[culm + j];
            }
            
            culm += i;
            
            send_packet(send);
        }
        vector<bool> snd(31);
        
        for (int j = 0; j < 8; j++){
            snd[blank[j]] = C[culm + j];
        }
        
        send_packet(snd);
    }
    vector<bool> send(31);
    int cur = 0;
    for (int i = 0; i < 31; i++){
        if (C[i] == 0){
            send[i] = (sz >> cur) & 1;
            cur++;
        }
    }
    send_packet(send);
    for (int i = 0; i < sz; i += 16){
        vector<bool> send(31);
        int cur = 0;
        for (int j = 0; j < 31; j++){
            if (C[j] == 0){
                send[j] = M[(i + cur) % sz];
                cur++;
            }
        }
        send_packet(send);
    }
}

vector<bool> receive_message(vector<vector<bool>> R){
    vector<int> C(31);
    vector<int> blank;
    int c = 0;
    for (int i = 0; i < 31; i++){
        c += R[0][i];
    }
    if (c >= 16){
        c = 1;
    }
    else{
        c = 0;
    }
    if (c == 0){
        for (int i = 0; i < 9; i++){
            int c0 = 0, c1 = 0;
            for (int j = 0; j < 31; j++){
                if (R[i + 1][j] == 1){
                    if (j % 2== 1){
                        c1++;
                    }
                    else{
                        c0++;
                    }
                }
            }
            if (c1 >= c0){
                C[i] = 1;
            }
            else{
                blank.push_back(i);
            }
        }
        int culm = 9;
        for (int i = 2; i < 16; i *= 2){
            
            int lg = log2(i);
            
            for (int j = 0; j < i; j++){
                C[culm + j] = R[9 + lg][blank[j]];
                if (C[culm + j] == 0){
                    blank.push_back(culm + j);
                }
            }
            culm += i;
        }
        for (int j = 0; j < 8; j++){
            C[culm + j] = R[9 + 4][blank[j]];
            if (C[culm + j] == 0){
                blank.push_back(culm + j);
            }
        }
    }
    else{
        for (int i = 0; i < 9; i++){
            int c0 = 0, c1 = 0;
            for (int j = 0; j < 31; j++){
                if (R[i + 1][j] == 1){
                    if (j % 2== 1){
                        c1++;
                    }
                    else{
                        c0++;
                    }
                }
            }
            if (c1 >= c0){
                C[30 - i] = 1;
            }
            else{
                blank.push_back(30 - i);
            }
        }
        int culm = 9;
        for (int i = 2; i < 16; i *= 2){
            
            int lg = log2(i);
            
            for (int j = 0; j < i; j++){
                C[30 - (culm + j)] = R[9 + lg][blank[j]];
                if (C[30 - (culm + j)] == 0){
                    blank.push_back(30 - (culm + j));
                }
            }
            culm += i;
        }
        for (int j = 0; j < 8; j++){
            C[30 - (culm + j)] = R[9 + 4][blank[j]];
            if (C[30 - (culm + j)] == 0){
                blank.push_back(30 - (culm + j));
            }
        }
    }
    int sz = 0;
    int cur = 0;
    for (int i = 0; i < 31; i++){
        if (C[i] == 0){
            sz += (1 << cur) * R[14][i];
            cur++;
        }
    }
    vector<bool> ans(sz);
    cur = 0;
    for (int i = 15; i < R.size(); i++){
        for (int j = 0; j < 31; j++){
            if (C[j] == 0){
                ans[cur % sz] = R[i][j];
                cur++;
            }
        }
    }
    return ans;
}

/*
 ____   ___    ___     ____  _____          ____    ____   ___
|      |   |  |   \   |        |     /|    |       |      |   \
|      |   |  |    |  |____    |      |    |   _   |____  |___/
|      |   |  |    |  |        |      |    |    |  |      |  \
|____  |___|  |___/   |____    |    __|__  |____|  |____  |   \
 
*/

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