Submission #1207863

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207863		lighton	Flight to the Ford (BOI22_communication)	C++20	100 / 100	1004 ms	3380 KiB

communication

#include"communication.h"
#include<bits/stdc++.h>
#define pb push_back
#define all(v) v.begin(),v.end()
#define forf(i,s,e) for(int i = s; i<=e; i++)
#define forb(i,s,e) for(int i = s; i>=e; i--)
#define idx(i,v) (int)(lower_bound(all(v),i)-v.begin())
#define comp(v) v.erase(unique(all(v)),v.end())
#define sz(v) (int)v.size()
#define fs first
#define se second
#define SP << " " <<
#define LN << "\n"
#define IO cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false);
using namespace std;
typedef long long ll;
ll inf = 1e18;

vector<int> message[4] =
        {{0,0,0,0},
         {0,1,1,0},
         {1,0,0,1},
         {1,1,1,1}};
vector<int> contrast(vector<int> R){
    vector<int> ret;
    forf(x,0,3){
        int f = 1;
        forf(i,0,2) if(R[i]!=message[x][i] && R[i+1]!=message[x][i+1]) f = 0;
        if(f) ret.pb(x);
    }
    return ret;
}

vector<int> enc(int Tc, int Tw, int X){
    if(Tc+Tw==2) return {0,1};
    if(Tc+Tw==1) return {0};
    if(Tc+Tw<=8) {
        int p[5];
        forf(i,0,4) p[i] = (double)(Tc+Tw) / 4 * i;
        int I;
        forf(i,0,4) if(X>=p[i]) I = i;

        vector<int> R;
        forf(i,0,3) R.pb(send(message[I][i]));
        vector<pair<int,int> > intv;
        int nN=0,nX=0;
        for(auto i : contrast(R)) intv.pb({p[i],p[i+1]}), nN += p[i+1]-p[i];
        if(X < intv[0].se) nX = X-intv[0].fs;
        else nX = intv[0].se-intv[0].fs + X-intv[1].fs;

        vector<int> res = enc(nN,0,nX);
        vector<int> ret;
        for(auto i : res){
            if(i < intv[0].se-intv[0].fs) ret.pb(intv[0].fs+i);
            else ret.pb(intv[1].fs+ i-(intv[0].se-intv[0].fs));
        }
        return ret;
    }

    int nTc, nTw, nX; vector<int> res,ret;

    if(X < Tc/2 || (Tc <= X && X < Tc+Tw/2)){
        if(send(1)){
            nTc = Tc/2+Tw/2, nTw = Tc-Tc/2;
            if(X < Tc/2) nX = X;
            else nX = Tc/2 + X-Tc;
            res = enc(nTc, nTw , nX);
            for(auto i : res){
                if(i < Tc/2) ret.pb(i);
                else ret.pb(Tc + i-Tc/2);
            }
        }
        else{
            nTc = Tc+Tw-Tc/2-Tw/2, nTw = Tc/2;
            nX = nTc+X;
            res = enc(nTc, nTw , nX);
            for(auto i : res) ret.pb(i-nTc);
        }
    }
    else{
        if(send(0) == 0){
            nTc = Tc+Tw-Tc/2-Tw/2, nTw = Tc/2;
            if(X < Tc) nX = X-Tc/2;
            else nX = Tc-Tc/2 + X-(Tc+Tw/2);
            res = enc(nTc, nTw, nX);
            for(auto i : res){
                if(i < Tc-Tc/2) ret.pb(i+Tc/2);
                else ret.pb(Tc+Tw/2 + i-(Tc-Tc/2));
            }
        }
        else{
            nTc = Tc/2+Tw/2, nTw = Tc-Tc/2;
            nX = nTc+X-Tc/2;
            res = enc(nTc, nTw , nX);
            for(auto i : res) ret.pb(i+Tc/2 - nTc);
        }
    }
    return ret;
}

vector<int> dec(int Tc,int Tw){
    if(Tc+Tw==2) return {0,1};
    if(Tc+Tw==1) return {0};
    if(Tc+Tw<= 8) {
        int p[5];
        forf(i,0,4) p[i] = (double)(Tc+Tw) / 4 * i;

        vector<int> R;
        forf(i,0,3) R.pb(receive());
        vector<pair<int,int> > intv;
        int nN=0;
        for(auto i : contrast(R)) intv.pb({p[i],p[i+1]}), nN += p[i+1]-p[i];

        vector<int> res = dec(nN,0);
        vector<int> ret;
        for(auto i : res){
            if(i < intv[0].se-intv[0].fs) ret.pb(intv[0].fs+i);
            else ret.pb(intv[1].fs+ i-(intv[0].se-intv[0].fs));
        }
        return ret;
    }
    int nTc, nTw, nX; vector<int> res,ret;
    if(receive()){
        nTc = Tc/2+Tw/2, nTw = Tc-Tc/2;
        res = dec(nTc,nTw);
        for(auto i : res) {
            if (i < nTc) {
                if(i < Tc/2) ret.pb(i);
                else ret.pb(Tc + i-Tc/2);
            }
            else ret.pb(i+Tc/2 - nTc);
        }
    }
    else{
        nTc = Tc+Tw-Tc/2-Tw/2, nTw = Tc/2;
        res = dec(nTc,nTw);
        for(auto i : res) {
            if (i < nTc) {
                if(i < Tc-Tc/2) ret.pb(i+Tc/2);
                else ret.pb(Tc+Tw/2 + i-(Tc-Tc/2));
            }
            else ret.pb(i-nTc);
        }
    }
    return ret;
}

void encode(int N, int X) {
    auto trash = enc(N,0,X-1);
}

std::pair<int, int> decode(int N) {
    vector<int> ans = dec(N,0);
    sort(all(ans));

    if(sz(ans)== 1) return {ans[0]+1,ans[0]+1};
    else return {ans[0]+1, min(ans[1]+1,N)};
}

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