Submission #1178139

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178139		alexander707070	Message (IOI24_message)	C++20	58.63 / 100	453 ms	872 KiB

message

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

#include "message.h"

vector<int> poss,bad;

vector<int> perms[8]={{12,1,9,24,0,27,25,21,29,15,18,28,14,13,23,16,26,3,20,17,8,19,22,10,30,7,6,11,5,4,2},{9,8,12,2,13,19,26,6,14,16,15,28,1,17,21,11,20,7,24,4,29,22,10,18,27,23,5,0,30,25,3},{17,9,11,12,27,22,26,19,8,21,30,25,18,4,5,1,20,24,28,10,3,14,6,7,16,15,2,23,0,13,29},{0,17,20,5,15,14,18,28,30,23,27,21,19,10,8,11,12,25,6,22,29,4,16,1,2,9,26,13,3,24,7},{6,10,21,25,8,16,19,22,2,13,28,24,15,4,3,30,23,0,29,7,20,9,14,18,5,12,26,1,11,17,27},{8,0,7,16,22,28,23,10,25,2,24,20,30,29,18,13,14,9,17,3,1,21,19,4,6,27,15,12,11,26,5},{9,6,8,19,11,17,16,14,27,21,7,15,20,3,30,13,5,28,24,18,23,22,0,4,1,29,25,12,26,10,2},{18,20,9,21,12,4,24,29,13,0,7,6,28,27,22,30,2,3,5,19,17,23,25,1,16,15,14,11,10,8,26}};
bool sp[32];

void reset(){
    poss.clear();
    bad.clear();

    for(int i=0;i<32;i++)sp[i]=false;
}

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

int calc(vector<int> s){
    int ones=0,qs=0,sz=0;
    for(int i=0;i<s.size();i+=max(ones,1)){
        ones=sz;

        for(int f=i;f<min(int(s.size()),i+max(ones,1));f++){
            if(!sp[s[f]])sz++;
        }

        qs++;
    }

    return qs;
}

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);
            sp[i]=true;
        }
    }

    int best=31,opt=0;
    for(int i=0;i<4;i++){
        if(calc(perms[i])<best){
            best=calc(perms[i]);
            opt=i;
        }
    }

    vector<int> p=perms[opt];

    int ones=0;
    vector<int> where;

    for(int i=0;i<2;i++){
        vector<bool> t(31,0);
        if(opt%2==1){
            for(int f=0;f<31;f++)t[f]=true;
        }

        send_packet(t);
        opt/=2;
    }

    for(int i=0;i<p.size();i+=max(ones,1)){
        ones=int(where.size());

        bool major=false;
        if(ones<=1)major=true;

        vector<bool> t(31,0);
        
        if(major){
            if(!sp[p[i]]){
                for(int f=0;f<31;f++)t[f]=true;
                where.push_back(p[i]);
            }

            send_packet(t);
            continue;
        }

        for(int f=i;f<min(int(p.size()),i+ones);f++){
            if(!sp[p[f]]){
                t[where[f-i]]=true;
                where.push_back(p[f]);
            }else{
                t[where[f-i]]=false;
            }
        }

        send_packet(t);
    }

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

    int opt=0;
    for(int i=0;i<2;i++){
        int bal=0;
        for(int f=0;f<31;f++){
            if(R[i][f])bal++;
            else bal--;
        }

        if(bal>0)opt+=(1<<i);
    }

    vector<int> p=perms[opt];

    int ones=0,step=2;
    vector<int> where;

    for(int i=0;i<p.size();i+=max(ones,1)){
        ones=int(where.size());

        bool major=false;
        if(ones<=1)major=true;
        
        if(major){

            int bal=0;
            for(int f=0;f<31;f++){
                if(R[step][f])bal++;
                else bal--;
            }
            
            if(bal>0){
                where.push_back(p[i]);
            }

            step++;
            continue;
        }

        for(int f=i;f<min(int(p.size()),i+max(ones,1));f++){
            if(R[step][where[f-i]]){
                where.push_back(p[f]);
            }
        }

        step++;
    }

    for(int i:where)poss.push_back(i);
    sort(poss.begin(),poss.end());

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

    vector<bool> mess;
    for(int i=step+1;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: 48.6324 / 90