#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][40];
int i;
for(i=0;i<19;i++)
{
int j;
for(j=0;j<40;j++)
{
v*=12972;
v+=125792;
v%=125972043;
arr[i][j]=!(v&(1<<16));
}
}
for(i=0;i<40;i++)
{
send(arr[X][i]);
}
}
std::pair<int, int> decode(int N)
{
srand(1);
long long v=125;
int arr[33][40];
int i;
for(i=0;i<19;i++)
{
int j;
for(j=0;j<40;j++)
{
v*=12972;
v+=125792;
v%=125972043;
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<158;i++)
{
r.push_back(receive());
}
vector<int>st;
for(i=0;i<19;i++)
{
int bef=0;
int j;
for(j=0;j<40;j++)
{
if(bef&&(r[j+118]!=arr[i][j]))
break;
bef=r[j+118]!=arr[i][j];
}
if(j==40)
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 |
118 ms |
1756 KB |
Output is correct |
| 2 |
Correct |
145 ms |
1752 KB |
Output is correct |
| 3 |
Correct |
384 ms |
1976 KB |
Output is correct |
| 4 |
Correct |
168 ms |
1868 KB |
Output is correct |
| 5 |
Correct |
247 ms |
1972 KB |
Output is correct |
| 6 |
Correct |
576 ms |
1904 KB |
Output is correct |
| 7 |
Correct |
1055 ms |
1752 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
852 ms |
1736 KB |
Output is partially correct |
| 2 |
Partially correct |
574 ms |
1880 KB |
Output is partially correct |
| 3 |
Partially correct |
734 ms |
1884 KB |
Output is partially correct |
| 4 |
Partially correct |
1420 ms |
1724 KB |
Output is partially correct |
| 5 |
Partially correct |
1141 ms |
1804 KB |
Output is partially correct |
| 6 |
Partially correct |
1083 ms |
1776 KB |
Output is partially correct |
| 7 |
Partially correct |
3576 ms |
1964 KB |
Output is partially correct |
| 8 |
Partially correct |
5743 ms |
2156 KB |
Output is partially correct |
| 9 |
Partially correct |
4890 ms |
1924 KB |
Output is partially correct |
| 10 |
Partially correct |
4786 ms |
1904 KB |
Output is partially correct |
| 11 |
Partially correct |
4466 ms |
1968 KB |
Output is partially correct |
| 12 |
Partially correct |
4564 ms |
1972 KB |
Output is partially correct |
| 13 |
Partially correct |
4177 ms |
1996 KB |
Output is partially correct |
| 14 |
Partially correct |
4058 ms |
1808 KB |
Output is partially correct |
| 15 |
Incorrect |
575 ms |
292 KB |
Not correct |
| 16 |
Halted |
0 ms |
0 KB |
- |
