Submission #651335

#	Time	Username	Problem	Language	Result	Execution time	Memory
651335		TimDee	Flight to the Ford (BOI22_communication)	C++17	15 / 100	37 ms	1820 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);
}
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)));
            }
        }
        //cout<<x<<": ";
        //for (auto p:dp[x][len-1][0]) cout<<p<<' ';
        //for (auto p:dp[x][len-1][1]) cout<<p<<' ';
        //cout<<'\n';
    }

    int x=0;
    for (int i=0; i<4; ++i) {
        int b=receive();
        x<<=1;
        x+=b;
    }
    vector<int> ans;
    for (auto v:dp[0][len-1][0]) if (x==v) ans.push_back(1);
    for (auto v:dp[0][len-1][1]) if (x==v) ans.push_back(1);
    for (auto v:dp[6][len-1][0]) if (x==v) ans.push_back(2);
    for (auto v:dp[6][len-1][1]) if (x==v) ans.push_back(2);
    for (auto v:dp[9][len-1][0]) if (x==v) ans.push_back(3);
    for (auto v:dp[9][len-1][1]) if (x==v) ans.push_back(3);

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

}

void encode(int n, int x) {
    
    if (x==1) {
        send(0); send(0); send(0); send(0);
    } else if (x==2) {
        send(0); send(1); send(1); send(0);
    } else {
        send(1); send(0); send(0); send(1);
    }

    

    /*
    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) {
                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]) {
                            paiu|=(x==y)&&(z==y);
                        }
                        for (auto z:dp[k][len-1][1]) {
                            paiu|=(x==y)&&(z==y);
                        }
                    }
                    for (auto y:dp[j][len-1][1]) {
                        for (auto z:dp[k][len-1][0]) {
                            paiu|=(x==y)&&(z==y);
                        }
                        for (auto z:dp[k][len-1][1]) {
                            paiu|=(x==y)&&(z==y);
                        }
                    }
                }
                for (auto x:dp[i][len-1][1]) {
                    for (auto y:dp[j][len-1][0]) {
                        for (auto z:dp[k][len-1][0]) {
                            paiu|=(x==y)&&(z==y);
                        }
                        for (auto z:dp[k][len-1][1]) {
                            paiu|=(x==y)&&(z==y);
                        }
                    }
                    for (auto y:dp[j][len-1][1]) {
                        for (auto z:dp[k][len-1][0]) {
                            paiu|=(x==y)&&(z==y);
                        }
                        for (auto z:dp[k][len-1][1]) {
                            paiu|=(x==y)&&(z==y);
                        }
                    }
                }
                if (paiu==0) {
                    cout<<"! "<<i<<' '<<j<<' '<<k<<'\n';
                }
            }
        }
    }
    */

}

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