Submission #1216405

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216405		hengliao	Message (IOI24_message)	C++20	61.19 / 100	494 ms	888 KiB

message

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

#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
#define pb push_back

typedef int ll;

namespace{
    const ll n=31;
}

void send_message(vector<bool> M, vector<bool> C) {
    vll lev(n);
    vll v;
    for(ll i=0;i<n;i++){
        if(C[i]==0){
            v.pb(i);
        }
    }
    ll lf=16;
    set<ll> st;
    for(ll i=0;i<n;i++){
        st.insert(i);
    }
    ll lv=0;
    while(lf<(ll) st.size()){
        // cout<<"currently lf: "<<lf<<" lv: "<<lv<<'\n';
        // cout<<"in set\n";
        // for(auto &it:st){
        //     cout<<it<<' ';
        // }
        // cout<<'\n';
        ll cnt=0;
        vector<bool> o(n);
        for(auto &it:st){
            if(C[it]==0){
                o[it]=1;
                cnt++;
            }
            if(cnt>=lf/2){
                break;
            }
        }
        vector<bool> re=send_packet(o);
        cnt=0;
        for(ll i=0;i<n;i++){
            if(st.find(i)==st.end()) continue;
            if(re[i]) cnt++;
        } 
        if(cnt<=(ll) st.size()/2){
            for(ll i=0;i<n;i++){
                if(st.find(i)==st.end()) continue;
                if(!re[i]){
                    lev[i]=lv;
                    st.erase(i);
                }
            }
        }
        else{
            for(ll i=0;i<n;i++){
                if(st.find(i)==st.end()) continue;
                if(re[i]){
                    lev[i]=lv;
                    st.erase(i);
                }
            }
        }
        lv++;
        lf/=2;
    }
    for(auto &it:st){
        lev[it]=lv;
    }
    vll ord(n);
    auto compare=[&](ll x, ll y){
        if(lev[x]!=lev[y]){
            return lev[x]>lev[y];
        }
        return x<y;
    };
    for(ll i=0;i<n;i++){
        ord[i]=i;
    }
    sort(ord.begin(), ord.end(), compare);
    ll pt=st.size();
    while(pt<n){
        ll siz=st.size();
        vll dumb;
        for(ll rep=0;rep<siz;rep++){
            dumb.pb(ord[pt]);
            pt++;
            if(pt>=n) break;
        }
        vector<bool> o(n);
        ll pt2=0;
        for(auto &it:st){
            if(pt2>=(ll) dumb.size()) break;
            if(C[dumb[pt2]]==0){
                o[it]=1;
            }
            pt2++;
        }
        send_packet(o);
        for(auto &it:dumb){
            if(C[it]==0){
                st.insert(it);
            }
        }
    }
    pt=0;

    // cout<<"good set:\n";

    // for(auto &it:st){
    //     cout<<it<<' ';
    // }
    // cout<<'\n';
    assert(st.size()==16);

    

    ll len=M.size();

    vector<bool> tep(n);

    for(auto &it:st){
        if(len&(1LL<<pt)){
            tep[it]=1;
        }
        pt++;
    }

    send_packet(tep);

    pt=0;
    while(pt<(ll) M.size()){
        vector<bool> o(n);
        for(auto &it:st){
            if(M[pt]){
                o[it]=1;
            }
            pt++;
            if(pt>=(ll) M.size()) break;
        }
        send_packet(o);
    }
}

vector<bool> receive_message(vector<vector<bool>> R) {
    
    vll lev(n);
    // vll v;
    // for(ll i=0;i<n;i++){
    //     if(C[i]==0){
    //         v.pb(i);
    //     }
    // }
    ll big=0;
    ll lf=16;
    set<ll> st;
    for(ll i=0;i<n;i++){
        st.insert(i);
    }
    ll lv=0;
    while(lf<(ll) st.size()){
        ll cnt=0;
        // vector<bool> o(n);
        // for(auto &it:st){
        //     if(C[it]==0){
        //         o[it]=1;
        //         cnt++;
        //     }
        //     if(cnt>=lf/2){
        //         break;
        //     }
        // }
        vector<bool> re=R[big];
        big++;
        cnt=0;
        for(ll i=0;i<n;i++){
            if(st.find(i)==st.end()) continue;
            if(re[i]) cnt++;
        } 
        if(cnt<=(ll) st.size()/2){
            for(ll i=0;i<n;i++){
                if(st.find(i)==st.end()) continue;
                if(!re[i]){
                    lev[i]=lv;
                    st.erase(i);
                }
            }
        }
        else{
            for(ll i=0;i<n;i++){
                if(st.find(i)==st.end()) continue;
                if(re[i]){
                    lev[i]=lv;
                    st.erase(i);
                }
            }
        }
        lv++;
        lf/=2;
    }
    for(auto &it:st){
        lev[it]=lv;
    }
    vll ord(n);
    auto compare=[&](ll x, ll y){
        if(lev[x]!=lev[y]){
            return lev[x]>lev[y];
        }
        return x<y;
    };
    for(ll i=0;i<n;i++){
        ord[i]=i;
    }
    sort(ord.begin(), ord.end(), compare);
    ll pt=st.size();
    while(pt<n){
        ll siz=st.size();
        vll dumb;
        for(ll rep=0;rep<siz;rep++){
            dumb.pb(ord[pt]);
            pt++;
            if(pt>=n) break;
        }
        // vector<bool> o(n);
        // ll pt2=0;
        // for(auto &it:st){
        //     if(pt2>=(ll) dumb.size()) break;
        //     if(C[dumb[pt2]]==0){
        //         o[it]=1;
        //     }
        //     pt2++;
        // }
        // send_packet(o);
        vector<bool> re=R[big];
        big++;
        ll pt2=0;
        vll dumb2;
        for(auto &it:st){
            if(pt2>=(ll) dumb.size()) break;
            if(re[it]==1){
                dumb2.pb(dumb[pt2]);
            }
            pt2++;
        }
        for(auto &it:dumb2){
            // if(C[it]==0){
            st.insert(it);
            // }
        }
    }
    pt=0;
    assert(st.size()==16);

    ll len=0;

    vector<bool> tep=R[big];
    big++;

    for(auto &it:st){
        if(tep[it]==1){
            len|=(1LL<<pt);
        }
        pt++;
    }

    // send_packet(tep);
    vector<bool> ans(len);
    pt=0;
    while(pt<len){
        vector<bool> re=R[big];
        big++;
        for(auto &it:st){
            if(re[it]){
                ans[pt]=1;
            }
            pt++;
            if(pt>=len) break;
        }
        // send_packet(o);
    }
    return ans;
    // return vector<bool> (n);
}

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