Submission #601755

#	Time	Username	Problem	Language	Result	Execution time	Memory
601755		jjang36524	Flight to the Ford (BOI22_communication)	C++17	40.67 / 100	5257 ms	2280 KiB

communication

#include"communication.h"
//
// --- Sample implementation for the task communication ---
//
// To compile this program with the sample grader, place:
//     communication.h communication_sample.cpp sample_grader.cpp
// in a single folder, then open the terminal in this directory (right-click onto an empty spot in the directory,
// left click on "Open in terminal") and enter e.g.:
//     g++ -std=c++17 communication_sample.cpp sample_grader.cpp
// in this folder. This will create a file a.out in the current directory which you can execute from the terminal
// as ./a.out
// See task statement or sample_grader.cpp for the input specification
//
#include <bits/stdc++.h>
using namespace std;
void encode(int N, int X)
{
    int lim=1000000002;
    while(lim>19)
    {
        int dp[40];
        int i;
        vector<int>x;
        for(i=0;;i++)
        {
            if((1<<i)>=lim)
                break;
            x.push_back(send((X>>i)&1));
        }
        int v=i;
        dp[0]=1;
        dp[1]=2;
        for(i=2;i<=v;i++)
        {
            dp[i]=dp[i-1]+dp[i-2];
        }
        int nlim=0;
        int nx=0;
        for(i=0;i<x.size();i++)
        {
            if(i!=x.size()&&x[i]!=((X>>i)&1))
            {
                nx+=dp[i];
            }
            nlim+=dp[i];
        }
        X=nx;
        lim=nlim;
    }
    long long v=125;
    int arr[33][50];
    int i;
    for(i=0;i<19;i++)
    {
        int j;
        for(j=0;j<50;j++)
        {
            v*=1272;
            v+=125792;
            v%=12592043;
            arr[i][j]=!(v&(1<<16));
        }
    }
    for(i=0;i<50;i++)
    {
        send(arr[X][i]);
    }
}
 
std::pair<int, int> decode(int N)
{
    srand(1);
    long long v=125;
    int arr[33][50];
    int i;
    for(i=0;i<19;i++)
    {
        int j;
        for(j=0;j<50;j++)
        {
            v*=1272;
            v+=125792;
            v%=12592043;
            arr[i][j]=!(v&(1<<16));
        }
    }
    int lim=1000000002;
    vector<int>lims;
    vector<int>vs;
    while(lim>19)
    {
        lims.push_back(lim);
        int dp[40];
        dp[0]=1;
        dp[1]=2;
        int i;
        for(i=0;;i++)
        {
            if((1<<i)>=lim)
                break;
        }
        int v=i;
        vs.push_back(v);
        for(i=2;i<=v;i++)
        {
            dp[i]=dp[i-1]+dp[i-2];
        }
        int nlim=0;
        for(i=0;i<v;i++)
        {
            nlim+=dp[i];
        }
        lim=nlim;
 
    }
    vector<int>r;
    for(i=0;i<168;i++)
    {
        r.push_back(receive());
    }
    vector<int>st;
    for(i=0;i<19;i++)
    {
        int bef=0;
        int j;
        for(j=0;j<50;j++)
        {
            if(bef&&(r[j+118]!=arr[i][j]))
                break;
            bef=r[j+118]!=arr[i][j];
        }
        if(j==50)
            st.push_back(i);
    }
    pair<int,int>ans={1,1};
    for(i=0;i<st.size();i++)
    {
        vector<int>nvs=vs;
        vector<int>nr=r;
        int cur=118;
        int nv=st[i];
        while(cur)
        {
            int bc=cur-1;
            cur-=vs.back();
            vs.pop_back();
            int j;
            int dp[40];
            dp[0]=1;
            dp[1]=2;
            int nnv=0;
            int i;
            for(i=2;i<=39;i++)
            {
                dp[i]=dp[i-1]+dp[i-2];
            }
            for(j=bc;j>=cur;j--)
            {
                if(nv>=dp[j-cur])
                {
                    r[j]^=1;
                    nv-=dp[j-cur];
                }
            }
            for(j=cur;j<=bc;j++)
            {
                nnv+=r[j]<<(j-cur);
            }
            nv=nnv;
        }
        vs=nvs;
        r=nr;
        if(i==0)
            ans.first=nv;
        else
            ans.second=nv;
    }
    ans.first=min(ans.first,N);
    ans.second=min(ans.second,N);
    ans.first=max(ans.first,1);
    ans.second=max(ans.second,1);
    return ans;
}

Compilation message (stderr)

communication.cpp: In function 'void encode(int, int)':
communication.cpp:39:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         for(i=0;i<x.size();i++)
      |                 ~^~~~~~~~~
communication.cpp:41:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |             if(i!=x.size()&&x[i]!=((X>>i)&1))
      |                ~^~~~~~~~~~
communication.cpp: In function 'std::pair<int, int> decode(int)':
communication.cpp:136:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |     for(i=0;i<st.size();i++)
      |             ~^~~~~~~~~~

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