제출 #1178121

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1178121		alexander707070	Message (IOI24_message)	C++20	43.96 / 100	501 ms	868 KiB

message

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

#include "message.h"

mt19937 rng(42069);

vector<int> poss,bad;

const int numz[20]={131032425,1621106528,1801346233,208804592,1622175430,567472974,916987615,2032970255,1391493477,560784608,1139582774,770562203,1059812424,696000454,1857587133,510455171,1321534373,1988621317,1692182411,2110794038};
int nums[20];

bool can[32];

void reset(){
    poss.clear();
    bad.clear();
    for(int i=0;i<20;i++)nums[i]=numz[i];

    for(int i=0;i<32;i++)can[i]=true;
}

vector<bool> tonum(int x){
    vector<bool> s;
    for(int i=0;i<31;i++){
        s.push_back(x%2);
        x/=2;
    }
    
    return s;
}

vector<bool> tonum16(int x){
    vector<bool> s;
    for(int i=0;i<16;i++){
        s.push_back(x%2);
        x/=2;
    }
    
    return s;
}

void sendbits(vector<bool> s){
    vector<bool> w(31,0);

    for(int i=0;i<s.size();i++){
        w[poss[i]]=s[i];
    }

    send_packet(w);
}

void send_message(vector<bool> M, vector<bool> C) {
    reset();

    for(int i=0;i<C.size();i++){
        if(!C[i])poss.push_back(i);
        else bad.push_back(i);
    }

    for(int i=0;i<20;i++){
        for(int f:bad){
            if(rng()%2==0)nums[i]^=(1<<f);
        }

        send_packet(tonum(nums[i]));
    }

    int sz=int(M.size());
    sendbits(tonum16(sz));

    for(int i=0;i<sz;i+=16){
        vector<bool> s;
        for(int f=i;f<min(sz,i+16);f++){
            s.push_back(M[f]);
        }

        sendbits(s);
    }
}

vector<bool> receive_message(vector< vector<bool> > R){
    reset();

    for(int i=0;i<20;i++){

        for(int f=0;f<31;f++){
            if(bool(nums[i]%2) != R[i][f])can[f]=false;
            nums[i]/=2;
        }
    }

    for(int i=0;i<31;i++){
        if(can[i])poss.push_back(i);
    }

    int sz=0;
    for(int i=0;i<16;i++){
        sz+=(1<<i) * int(R[20][poss[i]]);
    }

    vector<bool> mess;
    for(int i=21;i<R.size();i++){
        for(int f=0;f<16;f++){
            mess.push_back(R[i][poss[f]]);
        }
    }

    while(mess.size()>sz)mess.pop_back();

    return mess;
}

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