Submission #651675

#	Time	Username	Problem	Language	Result	Execution time	Memory
651675		TimDee	Flight to the Ford (BOI22_communication)	C++17	47.33 / 100	5127 ms	4436 KiB

communication

#include"communication.h"
#include <bits/stdc++.h>
using namespace std;
#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)));
            }
        }
    }

    if (n==3) {
        vector<int> paiu={1,2,3};
        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(paiu[0]);
        for (auto v:dp[0][len-1][1]) if (v==x) ans.push_back(paiu[0]);
        for (auto v:dp[6][len-1][0]) if (v==x) ans.push_back(paiu[1]);
        for (auto v:dp[6][len-1][1]) if (v==x) ans.push_back(paiu[1]);
        for (auto v:dp[9][len-1][0]) if (v==x) ans.push_back(paiu[2]);
        for (auto v:dp[9][len-1][1]) if (v==x) ans.push_back(paiu[2]);
    
        if (ans.size()==1) ans.push_back(ans[0]);
        for (auto &x:ans) x=min(x,n);
        return {ans[0],ans[1]};
    }


    int sq=sqrt(n)+1;
    int first=0;
    int second=0;
    int a[40000], b[40000], a_sz=sq, b_sz=0;
    for (int i=0; i<sq; ++i) a[i]=i;
    
    while (a_sz>3) {
        int n=a_sz;
        int f=n/4+min(n%4,1);
        int s=2*(n/4)+min(n%4,2);
        int t=3*(n/4)+n%4;

        int A=!receive(),B=!receive();
        int y=(A<<1)+B;

        if (y==0) {
            for (int i=f; i<n; ++i) b[b_sz++]=a[i];
        } else if (y==1) {
            for (int i=0; i<f; ++i) b[b_sz++]=a[i];
            for (int i=s; i<n; ++i) b[b_sz++]=a[i];
        } else if (y==2) {
            for (int i=0; i<s; ++i) b[b_sz++]=a[i];
            for (int i=t; i<n; ++i) b[b_sz++]=a[i];
        } else {
            for (int i=0; i<t; ++i) b[b_sz++]=a[i];
        }
        forn(i,b_sz) a[i]=b[i];
        a_sz=b_sz;
        b_sz=0;
    }
    vector<int> tmp={a[0],a[1],a[2]};
    
    a_sz=sq, b_sz=0;
    for (int i=0; i<sq; ++i) a[i]=i;

    while (a_sz>3) {
        int n=a_sz;
        int f=n/4+min(n%4,1);
        int s=2*(n/4)+min(n%4,2);
        int t=3*(n/4)+n%4;

        int A=!receive(), B=!receive();
        int y=(A<<1)+B;

        if (y==0) {
            for (int i=f; i<n; ++i) b[b_sz++]=a[i];
        } else if (y==1) {
            for (int i=0; i<f; ++i) b[b_sz++]=a[i];
            for (int i=s; i<n; ++i) b[b_sz++]=a[i];
        } else if (y==2) {
            for (int i=0; i<s; ++i) b[b_sz++]=a[i];
            for (int i=t; i<n; ++i) b[b_sz++]=a[i];
        } else {
            for (int i=0; i<t; ++i) b[b_sz++]=a[i];
        }
        forn(i,b_sz) a[i]=b[i];
        a_sz=b_sz;
        b_sz=0;
    }
    vector<int> paiu;
    for (auto x:tmp) {
        forn(i,3) paiu.push_back(x+a[i]*sq);
    }

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

        int A=!receive(), B=!receive();
        int y=(A<<1)+B;

        if (y==0) {
            for (int i=f; i<n; ++i) b.push_back(paiu[i]);
        } else if (y==1) {
            forn(i,f) b.push_back(paiu[i]);
            for (int i=s; i<n; ++i) b.push_back(paiu[i]);
        } else if (y==2) {
            forn(i,s) b.push_back(paiu[i]);
            for (int i=t; i<n; ++i) b.push_back(paiu[i]);
        } else {
            forn(i,t) b.push_back(paiu[i]);
        }
        paiu=b;

    }

    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(paiu[0]);
    for (auto v:dp[0][len-1][1]) if (v==x) ans.push_back(paiu[0]);
    for (auto v:dp[6][len-1][0]) if (v==x) ans.push_back(paiu[1]);
    for (auto v:dp[6][len-1][1]) if (v==x) ans.push_back(paiu[1]);
    for (auto v:dp[9][len-1][0]) if (v==x) ans.push_back(paiu[2]);
    for (auto v:dp[9][len-1][1]) if (v==x) ans.push_back(paiu[2]);

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

}

void encode(int n, int x) {

    if (n==3) {
        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);
        }
        return;
    }

    int sq=sqrt(n)+1;
    int first=x%sq;
    int second=x/sq;
    int save = x;
    int a[40000], b[40000], a_sz=sq, b_sz=0;
    for (int i=0; i<sq; ++i) a[i]=i;

    //cout<<sq<<":\n";
    
    x=first;
    while (a_sz>3) {
        int n=a_sz;
        int f=n/4+min(n%4,1);
        int s=2*(n/4)+min(n%4,2);
        int t=3*(n/4)+n%4;
        int l=0, r=a_sz-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);
        }
        int y=(A<<1)+B;

        //forn(i,a_sz) cout<<a[i]<<' '; cout<<'\n';
        //cout<<f<<' '<<s<<' '<<t<<' '<<n<<"  "<<y<<'\n';

        if (y==0) {
            for (int i=f; i<n; ++i) b[b_sz++]=a[i];
        } else if (y==1) {
            for (int i=0; i<f; ++i) b[b_sz++]=a[i];
            for (int i=s; i<n; ++i) b[b_sz++]=a[i];
        } else if (y==2) {
            for (int i=0; i<s; ++i) b[b_sz++]=a[i];
            for (int i=t; i<n; ++i) b[b_sz++]=a[i];
        } else {
            for (int i=0; i<t; ++i) b[b_sz++]=a[i];
        }
        forn(i,b_sz) a[i]=b[i];
        a_sz=b_sz;
        b_sz=0;
    }
    //cout<<a[0]<<' '<<a[1]<<' '<<a[2]<<'\n';
    vector<int> tmp={a[0],a[1],a[2]};

    a_sz=sq, b_sz=0;
    for (int i=0; i<sq; ++i) a[i]=i;

    x=second;
    while (a_sz>3) {
        int n=a_sz;
        int f=n/4+min(n%4,1);
        int s=2*(n/4)+min(n%4,2);
        int t=3*(n/4)+n%4;
        int l=0, r=a_sz-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);
        }
        int y=(A<<1)+B;
        if (y==0) {
            for (int i=f; i<n; ++i) b[b_sz++]=a[i];
        } else if (y==1) {
            for (int i=0; i<f; ++i) b[b_sz++]=a[i];
            for (int i=s; i<n; ++i) b[b_sz++]=a[i];
        } else if (y==2) {
            for (int i=0; i<s; ++i) b[b_sz++]=a[i];
            for (int i=t; i<n; ++i) b[b_sz++]=a[i];
        } else {
            for (int i=0; i<t; ++i) b[b_sz++]=a[i];
        }
        forn(i,b_sz) a[i]=b[i];
        a_sz=b_sz;
        b_sz=0;
    }
    //cout<<a[0]<<' '<<a[1]<<' '<<a[2]<<'\n';
    vector<int> paiu;
    for (auto x:tmp) {
        forn(i,3) paiu.push_back(x+a[i]*sq);
    }

    sort(paiu.begin(), paiu.end());
    while (paiu.size()>3) {
        vector<int> b;
        int n=paiu.size();
        int f=n/4 + min(n%4,1);
        int s=2*(n/4) + min(n%4,2);
        int t=3*(n/4) + min(n%4,3);
        int l=0, r=n-1;
        while (l<r) {
            int mid=(l+r+1)>>1;
            if (paiu[mid]>save) 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);
        }
        int y=(A<<1)+B;

        if (y==0) {
            for (int i=f; i<n; ++i) b.push_back(paiu[i]);
        } else if (y==1) {
            forn(i,f) b.push_back(paiu[i]);
            for (int i=s; i<n; ++i) b.push_back(paiu[i]);
        } else if (y==2) {
            forn(i,s) b.push_back(paiu[i]);
            for (int i=t; i<n; ++i) b.push_back(paiu[i]);
        } else {
            forn(i,t) b.push_back(paiu[i]);
        }
        paiu=b;

    }

    if (paiu[0]==save) {
        send(0); send(0); send(0); send(0);
    } else if (paiu[1]==save) {
        send(0); send(1); send(1); send(0);
    } else {
        send(1); send(0); send(0); send(1);
    }

}

Compilation message (stderr)

communication.cpp: In function 'std::pair<int, int> decode(int)':
communication.cpp:49:9: warning: unused variable 'first' [-Wunused-variable]
   49 |     int first=0;
      |         ^~~~~
communication.cpp:50:9: warning: unused variable 'second' [-Wunused-variable]
   50 |     int second=0;
      |         ^~~~~~

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