Submission #823996

#	Time	Username	Problem	Language	Result	Execution time	Memory
823996		ttamx	Flight to the Ford (BOI22_communication)	C++17	74 / 100	2726 ms	2164 KiB

communication

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

using namespace std;

typedef pair<int,int> p2;

void encode(int N, int X){
    vector<int> val={0,6,9,15};
    vector<int> bit;
    vector<vector<int>> vec(16);
    for(int i=0;i<16;i++){
        bool ok=true;
        for(int j=0;j<3;j++)ok&=(i>>j&3)!=3;
        if(ok)bit.emplace_back(i);
    }
    for(int i=0;i<4;i++)for(auto x:bit)vec[val[i]^x].emplace_back(i);
    auto give=[&](int x){
        int num=0;
        for(int i=0;i<4;i++)num|=send(val[x]>>i&1)<<i;
        return vec[num];
    };
    function<void(vector<p2>)> sol=[&](vector<p2> itv){
        int sz=0;
        for(auto [l,r]:itv)sz+=r-l+1;
        if(sz<=2)return;
        sz=(sz+3)/4;
        int cnt=0,cur=0;
        vector<vector<p2>> block(4);
        for(auto [l,r]:itv){
            block[cur].emplace_back(l,r);
            cnt+=r-l+1;
            while(cnt>=sz){
                int dif=cnt-sz;
                block[cur].back().second-=dif;
                cur++;
                if(dif>0)block[cur].emplace_back(r-dif+1,r);
                cnt=dif;
            }
        }
        int id=0;
        for(int i=0;i<4;i++)for(auto [l,r]:block[i])if(l<=X&&X<=r)id=i;
        auto tmp=give(id);
        vector<p2> res=block[tmp[0]];
        for(auto x:block[tmp[1]])res.emplace_back(x);
        sol(res);
    };
    sol({{1,N}});
}

pair<int, int> decode(int N) {
    vector<int> val={0,6,9,15};
    vector<int> bit;
    vector<vector<int>> vec(16);
    for(int i=0;i<16;i++){
        bool ok=true;
        for(int j=0;j<3;j++)ok&=(i>>j&3)!=3;
        if(ok)bit.emplace_back(i);
    }
    for(int i=0;i<4;i++)for(auto x:bit)vec[val[i]^x].emplace_back(i);
    auto get=[&](){
        int num=0;
        for(int i=0;i<4;i++)num|=receive()<<i;
        return vec[num];
    };
    vector<int> ans;
    function<void(vector<p2>)> sol=[&](vector<p2> itv){
        int sz=0;
        for(auto [l,r]:itv)sz+=r-l+1;
        if(sz<=2){
            for(auto [l,r]:itv)for(int i=l;i<=r;i++)ans.emplace_back(i);
            while(ans.size()<2)ans.emplace_back(1);
            return;
        }
        sz=(sz+3)/4;
        int cnt=0,cur=0;
        vector<vector<p2>> block(4);
        for(auto [l,r]:itv){
            block[cur].emplace_back(l,r);
            cnt+=r-l+1;
            while(cnt>=sz){
                int dif=cnt-sz;
                block[cur].back().second-=dif;
                cur++;
                if(dif>0)block[cur].emplace_back(r-dif+1,r);
                cnt=dif;
            }
        }
        auto tmp=get();
        vector<p2> res=block[tmp[0]];
        for(auto x:block[tmp[1]])res.emplace_back(x);
        sol(res);
    };
    sol({{1,N}});
    return {ans[0],ans[1]};
}

• Subtask 1: 15 / 15
• Subtask 2: 59.00003 / 85