Submission #651339

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

communication

#include"communication.h"
#include <bits/stdc++.h>
using namespace std;
const int PAIU=100;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int a, int b) {
    return a+rng()%(b-a+1);
}
#define forn(i,n) for (int i=0; i<n; ++i)
pair<int,int> decode(int n) {
    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)));
            }
        }
    }

    vector<int> a; forn(i,n) a.push_back(i+1);
    while (a.size()>2) {
        //cout<<"iter\n";
        //for (auto x:a) cout<<x<<' '; cout<<'\n';

        int n=a.size();
        int f = n/3 + !!(n%3);
        int s = 2*(n/3) + ((n%3) == 2);

        int y=0;
        for (int i=0; i<4; ++i) {
            y<<=1; y+=receive();
        }

        vector<int> b;
        vector<int> match;
        for (auto v:dp[0][len-1][0]) if (v==y) {
            for (int i=0; i<f; ++i) b.push_back(a[i]);
        }
        for (auto v:dp[0][len-1][1]) if (v==y) {
            for (int i=0; i<f; ++i) b.push_back(a[i]);
        }
        for (auto v:dp[6][len-1][0]) if (v==y) {
            for (int i=f; i<s; ++i) b.push_back(a[i]);
        }
        for (auto v:dp[6][len-1][1]) if (v==y) {
            for (int i=f; i<s; ++i) b.push_back(a[i]);
        }
        for (auto v:dp[9][len-1][0]) if (v==y) {
            for (int i=s; i<n; ++i) b.push_back(a[i]);
        }
        for (auto v:dp[9][len-1][1]) if (v==y) {
            for (int i=s; i<n; ++i) b.push_back(a[i]);
        }
        a=b;

    }
    if (a.size()==1) a.push_back(a[0]);
    return {a[0],a[1]};

}

void encode(int n, int x) {

    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)));
            }
        }
        //if (x==0 || x==6 || x==9 || x==15) {
        //cout<<x<<": ";
        //for (auto p:dp[x][len-1][0]) cout<<p<<' ';
        //for (auto p:dp[x][len-1][1]) cout<<p<<' ';
        //cout<<'\n';
        //}
    }
    
    vector<int> a; forn(i,n) a.push_back(i+1);
    while (a.size()>2) {
        //cout<<"iter\n";
        //for (auto x:a) cout<<x<<' '; cout<<'\n';

        int n=a.size();
        int f = n/3 + !!(n%3);
        int s = 2*(n/3) + ((n%3) == 2);

        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 y=0;
        if (r<f) {
            y<<=1; y+=send(0);
            y<<=1; y+=send(0);
            y<<=1; y+=send(0);
            y<<=1; y+=send(0);
        } else if (r<s) {
            y<<=1; y+=send(0);
            y<<=1; y+=send(1);
            y<<=1; y+=send(1);
            y<<=1; y+=send(0);
        } else {
            y<<=1; y+=send(1);
            y<<=1; y+=send(0);
            y<<=1; y+=send(0);
            y<<=1; y+=send(1);
        }
        vector<int> b;
        vector<int> match;
        for (auto v:dp[0][len-1][0]) if (v==y) {
            for (int i=0; i<f; ++i) b.push_back(a[i]);
        }
        for (auto v:dp[0][len-1][1]) if (v==y) {
            for (int i=0; i<f; ++i) b.push_back(a[i]);
        }
        for (auto v:dp[6][len-1][0]) if (v==y) {
            for (int i=f; i<s; ++i) b.push_back(a[i]);
        }
        for (auto v:dp[6][len-1][1]) if (v==y) {
            for (int i=f; i<s; ++i) b.push_back(a[i]);
        }
        for (auto v:dp[9][len-1][0]) if (v==y) {
            for (int i=s; i<n; ++i) b.push_back(a[i]);
        }
        for (auto v:dp[9][len-1][1]) if (v==y) {
            for (int i=s; i<n; ++i) b.push_back(a[i]);
        }
        a=b;

    }

    return;
    
    for (int i=0; i<(1<<len); ++i) {
        for (int j=i+1; j<(1<<len); ++j) {
            for (int k=j+1; k<(1<<len); ++k) {
                for (int l=k+1; l<(1<<len); ++l) {
                    int paiu=0;
                    for (auto x:dp[i][len-1][0]) {
                        for (auto y:dp[j][len-1][0]) {
                            for (auto z:dp[k][len-1][0]) {
                                for (auto q:dp[l][len-1][0]) {
                                    paiu|=(x==y && y==z);
                                    paiu|=(x==y && y==q);
                                    paiu|=(x==z && z==q);
                                    paiu|=(y==z && z==q);
                                }
                                for (auto q:dp[l][len-1][1]) {
                                    paiu|=(x==y && y==z);
                                    paiu|=(x==y && y==q);
                                    paiu|=(x==z && z==q);
                                    paiu|=(y==z && z==q);
                                }
                            }
                            for (auto z:dp[k][len-1][1]) {
                                for (auto q:dp[l][len-1][0]) {
                                    paiu|=(x==y && y==z);
                                    paiu|=(x==y && y==q);
                                    paiu|=(x==z && z==q);
                                    paiu|=(y==z && z==q);
                                }
                                for (auto q:dp[l][len-1][1]) {
                                    paiu|=(x==y && y==z);
                                    paiu|=(x==y && y==q);
                                    paiu|=(x==z && z==q);
                                    paiu|=(y==z && z==q);
                                }
                            }
                        }
                        for (auto y:dp[j][len-1][1]) {
                            for (auto z:dp[k][len-1][0]) {
                                for (auto q:dp[l][len-1][0]) {
                                    paiu|=(x==y && y==z);
                                    paiu|=(x==y && y==q);
                                    paiu|=(x==z && z==q);
                                    paiu|=(y==z && z==q);
                                }
                                for (auto q:dp[l][len-1][1]) {
                                    paiu|=(x==y && y==z);
                                    paiu|=(x==y && y==q);
                                    paiu|=(x==z && z==q);
                                    paiu|=(y==z && z==q);
                                }
                            }
                            for (auto z:dp[k][len-1][1]) {
                                for (auto q:dp[l][len-1][0]) {
                                    paiu|=(x==y && y==z);
                                    paiu|=(x==y && y==q);
                                    paiu|=(x==z && z==q);
                                    paiu|=(y==z && z==q);
                                }
                                for (auto q:dp[l][len-1][1]) {
                                    paiu|=(x==y && y==z);
                                    paiu|=(x==y && y==q);
                                    paiu|=(x==z && z==q);
                                    paiu|=(y==z && z==q);
                                }
                            }
                        }
                    }
                    for (auto x:dp[i][len-1][1]) {
                        for (auto y:dp[j][len-1][0]) {
                            for (auto z:dp[k][len-1][0]) {
                                for (auto q:dp[l][len-1][0]) {
                                    paiu|=(x==y && y==z);
                                    paiu|=(x==y && y==q);
                                    paiu|=(x==z && z==q);
                                    paiu|=(y==z && z==q);
                                }
                                for (auto q:dp[l][len-1][1]) {
                                    paiu|=(x==y && y==z);
                                    paiu|=(x==y && y==q);
                                    paiu|=(x==z && z==q);
                                    paiu|=(y==z && z==q);
                                }
                            }
                            for (auto z:dp[k][len-1][1]) {
                                for (auto q:dp[l][len-1][0]) {
                                    paiu|=(x==y && y==z);
                                    paiu|=(x==y && y==q);
                                    paiu|=(x==z && z==q);
                                    paiu|=(y==z && z==q);
                                }
                                for (auto q:dp[l][len-1][1]) {
                                    paiu|=(x==y && y==z);
                                    paiu|=(x==y && y==q);
                                    paiu|=(x==z && z==q);
                                    paiu|=(y==z && z==q);
                                }
                            }
                        }
                        for (auto y:dp[j][len-1][1]) {
                            for (auto z:dp[k][len-1][0]) {
                                for (auto q:dp[l][len-1][0]) {
                                    paiu|=(x==y && y==z);
                                    paiu|=(x==y && y==q);
                                    paiu|=(x==z && z==q);
                                    paiu|=(y==z && z==q);
                                }
                                for (auto q:dp[l][len-1][1]) {
                                    paiu|=(x==y && y==z);
                                    paiu|=(x==y && y==q);
                                    paiu|=(x==z && z==q);
                                    paiu|=(y==z && z==q);
                                }
                            }
                            for (auto z:dp[k][len-1][1]) {
                                for (auto q:dp[l][len-1][0]) {
                                    paiu|=(x==y && y==z);
                                    paiu|=(x==y && y==q);
                                    paiu|=(x==z && z==q);
                                    paiu|=(y==z && z==q);
                                }
                                for (auto q:dp[l][len-1][1]) {
                                    paiu|=(x==y && y==z);
                                    paiu|=(x==y && y==q);
                                    paiu|=(x==z && z==q);
                                    paiu|=(y==z && z==q);
                                }
                            }
                        }
                    }
                    if (paiu==0) {
                        cout<<"! "<<i<<' '<<j<<' '<<k<<' '<<l<<'\n';
                    }
                }
            }
        }
    }
    

}

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