Submission #651665

#	Time	Username	Problem	Language	Result	Execution time	Memory
651665		TimDee	Flight to the Ford (BOI22_communication)	C++17	0 / 100	515 ms	118784 KiB

communication

#include"communication.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for (int i=0; i<n; ++i)
const int PAIU=15;
pair<int,int> decode(int n) {
    
    vector<vector<int>> paiu(PAIU);
    for (int bit=PAIU*2-1; bit>=0; bit-=2) {
        int p=!receive(), v=!receive();
        p<<=1; int y=p+v;
        forn(i,4) if (i!=y) paiu[bit/2].push_back(i);
    }

    vector<int> a={0};
    for (int bit=PAIU-1; bit>=0; --bit) {
        vector<int> b;
        forn(i,3) for (auto x:a) b.push_back((x<<2)+paiu[bit][i]);
        a=b;
    }

    sort(a.begin(), a.end());
    while (a.size()>3) {
        int n=a.size();
        int f=n/4 + !!(n%4);
        int s=2*(n/4) + (min(n%4,2));
        int t=3*(n/4) + n%4;

        vector<int> b;
        int A=!receive(),B=!receive();
        A<<=1;
        int v=A+B;

        if (v==3) {
            for (int i=0; i<t; ++i) b.push_back(a[i]);
        } else if (v==1) {
            for (int i=0; i<f; ++i) b.push_back(a[i]);
            for (int i=s; i<n; ++i) b.push_back(a[i]);
        } else if (v==2) {
            for (int i=0; i<s; ++i) b.push_back(a[i]);
            for (int i=t; i<n; ++i) b.push_back(a[i]);
        } else {
            for (int i=f; i<n; ++i) b.push_back(a[i]);
        }
        a=b;

    }
    while (a.size()<3) a.push_back(a.back());

    int len=4;
    vector<vector<vector<vector<int>>>> dp((1<<len),vector<vector<vector<int>>>(len,vector<vector<int>>(2)));

    for (int x=0; x<(1<<len); ++x) {
        dp[x][0][0].push_back(x&1);
        dp[x][0][1].push_back(!(x&1));
        for (int l=1; l<len; ++l) {
            for (auto v:dp[x][l-1][0]) {
                dp[x][l][0].push_back(v+(x&(1<<l)));
                dp[x][l][1].push_back(v+((!((x>>l)&1))<<l));
            }
            for (auto v:dp[x][l-1][1]) {
                dp[x][l][0].push_back(v+(x&(1<<l)));
            }
        }
    }

    int x=0;
    forn(i,4) {
        int f=receive();
        x<<=1; x+=f;
    }

    vector<int> ans;
    for (auto v:dp[0][len-1][0]) if (v==x) ans.push_back(a[0]);
    for (auto v:dp[0][len-1][1]) if (v==x) ans.push_back(a[0]);
    for (auto v:dp[6][len-1][0]) if (v==x) ans.push_back(a[1]);
    for (auto v:dp[6][len-1][1]) if (v==x) ans.push_back(a[1]);
    for (auto v:dp[9][len-1][0]) if (v==x) ans.push_back(a[2]);
    for (auto v:dp[9][len-1][1]) if (v==x) ans.push_back(a[2]);

    if (ans.size()==1) ans.push_back(ans[0]);
    for (auto &x:ans) x=min(x,n);
    return {ans[0],ans[1]};

}

vector<int32_t> a;
void bf(int x,vector<vector<int>>&paiu, int i) {
    if (i<0) {a.push_back(x); return;}
    for (auto y:paiu[i]) bf((x<<2)+y,paiu,i-1);
}

void encode(int n, int x) {

    vector<vector<int>> paiu(PAIU);
    for (int bit=PAIU*2-1; bit>=0; bit-=2) {
        int f=(x>>bit)&1;
        int s=(x>>(bit-1))&1;
        int p=!send(f), v=!send(s);
        p<<=1; int y=p+v;
        forn(i,4) if (i!=y) paiu[bit/2].push_back(i);
    }

    bf(0,paiu,PAIU-1);
    //cout<<a.size()<<' '; 
    //vector<int> a={0};
    //for (int bit=PAIU-1; bit>=0; --bit) {
    //    vector<int> b;
    //    forn(i,3) for (auto x:a) b.push_back((x<<2)+paiu[bit][i]);
    //    a=b;
    //}

    sort(a.begin(), a.end());
    vector<int> b;
    while (a.size()>3) {
        int n=a.size();
        int f=n/4 + !!(n%4);
        int s=2*(n/4) + (min(n%4,2));
        int t=3*(n/4) + n%4;

        int l=0, r=n-1;
        while (l<r) {
            int mid=(l+r+1)>>1;
            if (a[mid]>x) r=mid-1;
            else l=mid;
        }
        int A,B;
        if (r<f) {
            A=!send(0), B=!send(0);
        } else if (r<s) {
            A=!send(0), B=!send(1);
        } else if (r<t) {
            A=!send(1), B=!send(0);
        } else {
            A=!send(1), B=!send(1);
        }
        A<<=1;
        int v=A+B;

        if (v==3) {
            for (int i=0; i<t; ++i) b.push_back(a[i]);
        } else if (v==1) {
            for (int i=0; i<f; ++i) b.push_back(a[i]);
            for (int i=s; i<n; ++i) b.push_back(a[i]);
        } else if (v==2) {
            for (int i=0; i<s; ++i) b.push_back(a[i]);
            for (int i=t; i<n; ++i) b.push_back(a[i]);
        } else {
            for (int i=f; i<n; ++i) b.push_back(a[i]);
        }
        a=b;
        b.clear();
    }

    while (a.size()<3) a.push_back(a.back());
    if (x==a[0]) {
        send(0); send(0); send(0); send(0);
    } else if (x==a[1]) {
        send(0); send(1); send(1); send(0);
    } else {
        send(1); send(0); send(0); send(1);
    }
    exit(1);

}

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