제출 #1210442

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1210442		PagodePaiva	Message (IOI24_message)	C++20	58.63 / 100	477 ms	892 KiB

message

#include "message.h"
#include<bits/stdc++.h>

using namespace std;

vector <int> construct(vector <int> bons, vector <int> ruins){
    if(bons.size() == 1 and ruins.size() == 0){
        return bons;
    }
    int n = bons.size();
    vector <bool> A(31, 0);
    for(int i = 0;i < n/2;i++){
        A[bons[i]] = 1;
    }
    vector <bool> pacote = send_packet(A);
    vector <int> bons0, bons1;
    vector <int> ruins0, ruins1;
    for(auto x : bons){
        if(pacote[x] == 0)
            bons0.push_back(x);
        else
            bons1.push_back(x);
    }
    for(auto x : ruins){
        if(pacote[x] == 0)
            ruins0.push_back(x);
        else
            ruins1.push_back(x);
    }
    vector <int> pos;
    if(bons0.size() + ruins0.size() > bons1.size() + ruins1.size()){
        swap(bons0, bons1);
        swap(ruins0, ruins1);
    }
    pos = construct(bons0, ruins0);
    vector <pair<int, int>> posicoes;
    for(auto x : bons1)
        posicoes.push_back({x, 0});
    for(auto x : ruins1)
        posicoes.push_back({x, 1});
    sort(posicoes.begin(), posicoes.end());
    for(int i = 0;i < 31;i++){
        A[i] = 0;
    }
    int len = pos.size(), contador = 0;
    for(int i = 0;i < posicoes.size();i++){
        A[pos[contador]] = posicoes[i].second;
        contador++;
        if(contador == len){
            send_packet(A);
            for(int i = 0;i < 31;i++){
                A[i] = 0;
            }
            contador = 0;
        }
    }
    if(contador != 0){
        send_packet(A);
    }
    return bons;
}

void send_message(std::vector<bool> M, std::vector<bool> C) {
    vector <int> bons, ruins;
    for(int i = 0;i < C.size();i++){
        if(C[i])
            ruins.push_back(i);
        else
            bons.push_back(i);
    }  
    vector <int> pos = construct(bons, ruins);
    int n = M.size();
    vector <bool> A(31, 0);
    for(int bit = 0;bit < 16;bit++){
        if(((1<<bit)&n)){
            A[pos[bit]] = 1;
        }
    }
    send_packet(A);
    for(int i = 0;i < 31;i++)
        A[i] = 0;
    int contador = 0, len = pos.size();
    for(auto x : M){
        A[pos[contador]] = x;
        contador++;
        if(contador == len){
            send_packet(A);
            contador = 0;
            for(int i = 0;i < 31;i++)
                A[i] = 0;
        }
    }
    if(contador != 0){
        send_packet(A);
    }
    return;
}

vector <vector<bool>> pacotes;

vector <int> resposta(vector <int> mist, int &con){
    if(mist.size() == 1){
        return mist;
    }
    vector <bool> pacote = pacotes[con];
    con++;
    vector <int> zeros, uns;
    for(auto x : mist){
        if(pacote[x] == 0)
            zeros.push_back(x);
        else
            uns.push_back(x);
    }
    if(zeros.size() > uns.size())
        swap(zeros, uns);
    vector <int> pos = resposta(zeros, con);
    int contador = 0;
    pacote = pacotes[con];
    con++;
    vector <int> bons, ruins;
    int len = pos.size();
    for(int i = 0;i < uns.size();i++){
        if(pacote[pos[contador]] == 0){
            bons.push_back(uns[i]);
        }
        else{
            ruins.push_back(uns[i]);
        }
        contador++;
        if(contador == len){
            pacote = pacotes[con];
            con++;
            contador = 0;
        }
    }
    if(contador == 0)
        con--;
    for(auto x : bons){
        pos.push_back(x);
    }
    sort(pos.begin(), pos.end());
    return pos;
}   

std::vector<bool> receive_message(std::vector<std::vector<bool>> R) {
    pacotes = R;
    vector <int> mist;
    for(int i = 0;i < 31;i++){
        mist.push_back(i);
    }
    int con = 0;
    vector <int> bons = resposta(mist, con);
    int n = 0;
    vector <bool> pacote = pacotes[con];
    con++;
    for(int i = 0;i < 16;i++){
        if(pacote[bons[i]]){
            n |= (1<<i);
        }
    }
    pacote = pacotes[con];
    con++;
    int contador = 0;
    vector <bool> mensagem;
    for(int i = 0;i < n;i++){
        mensagem.push_back(pacote[bons[contador]]);
        contador++;
        if(contador == bons.size()){
            if(con != pacotes.size()) 
                pacote = pacotes[con];
            con++;
            contador = 0;
        }
    }
    return mensagem;
}

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