#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
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++)
| ~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
152 ms |
1756 KB |
Output is correct |
| 2 |
Correct |
174 ms |
1772 KB |
Output is correct |
| 3 |
Correct |
311 ms |
1728 KB |
Output is correct |
| 4 |
Correct |
173 ms |
1796 KB |
Output is correct |
| 5 |
Correct |
240 ms |
2092 KB |
Output is correct |
| 6 |
Correct |
609 ms |
1888 KB |
Output is correct |
| 7 |
Correct |
1282 ms |
1800 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
1433 ms |
1744 KB |
Output is partially correct |
| 2 |
Partially correct |
534 ms |
1716 KB |
Output is partially correct |
| 3 |
Partially correct |
658 ms |
1716 KB |
Output is partially correct |
| 4 |
Partially correct |
1357 ms |
1880 KB |
Output is partially correct |
| 5 |
Partially correct |
1118 ms |
1876 KB |
Output is partially correct |
| 6 |
Partially correct |
813 ms |
1844 KB |
Output is partially correct |
| 7 |
Partially correct |
3841 ms |
1968 KB |
Output is partially correct |
| 8 |
Partially correct |
5257 ms |
2280 KB |
Output is partially correct |
| 9 |
Partially correct |
5183 ms |
2048 KB |
Output is partially correct |
| 10 |
Partially correct |
4907 ms |
2004 KB |
Output is partially correct |
| 11 |
Partially correct |
4764 ms |
2116 KB |
Output is partially correct |
| 12 |
Partially correct |
5108 ms |
1964 KB |
Output is partially correct |
| 13 |
Partially correct |
4351 ms |
1932 KB |
Output is partially correct |
| 14 |
Partially correct |
4087 ms |
1920 KB |
Output is partially correct |
| 15 |
Partially correct |
2135 ms |
1928 KB |
Output is partially correct |
| 16 |
Partially correct |
4737 ms |
2004 KB |
Output is partially correct |
| 17 |
Partially correct |
1101 ms |
1912 KB |
Output is partially correct |
| 18 |
Partially correct |
1212 ms |
1960 KB |
Output is partially correct |
| 19 |
Partially correct |
1074 ms |
1860 KB |
Output is partially correct |
| 20 |
Partially correct |
1228 ms |
1776 KB |
Output is partially correct |
| 21 |
Partially correct |
1106 ms |
1728 KB |
Output is partially correct |
| 22 |
Partially correct |
1041 ms |
1852 KB |
Output is partially correct |
| 23 |
Partially correct |
1829 ms |
1952 KB |
Output is partially correct |
| 24 |
Correct |
103 ms |
1776 KB |
Output is correct |
| 25 |
Correct |
114 ms |
1668 KB |
Output is correct |
| 26 |
Correct |
254 ms |
1716 KB |
Output is correct |
| 27 |
Correct |
148 ms |
1764 KB |
Output is correct |
| 28 |
Correct |
216 ms |
1668 KB |
Output is correct |
| 29 |
Correct |
475 ms |
1868 KB |
Output is correct |
| 30 |
Correct |
1063 ms |
1680 KB |
Output is correct |
