#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*=12972;
v+=125792;
v%=125972043;
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*=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<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++)
| ~^~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
135 ms |
1660 KB |
Output is correct |
| 2 |
Correct |
178 ms |
1844 KB |
Output is correct |
| 3 |
Correct |
220 ms |
1888 KB |
Output is correct |
| 4 |
Correct |
156 ms |
1700 KB |
Output is correct |
| 5 |
Correct |
188 ms |
1840 KB |
Output is correct |
| 6 |
Correct |
587 ms |
1792 KB |
Output is correct |
| 7 |
Correct |
1073 ms |
1764 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Partially correct |
1092 ms |
1680 KB |
Output is partially correct |
| 2 |
Partially correct |
690 ms |
1664 KB |
Output is partially correct |
| 3 |
Partially correct |
727 ms |
1696 KB |
Output is partially correct |
| 4 |
Partially correct |
1190 ms |
1664 KB |
Output is partially correct |
| 5 |
Partially correct |
1170 ms |
1700 KB |
Output is partially correct |
| 6 |
Partially correct |
926 ms |
1660 KB |
Output is partially correct |
| 7 |
Partially correct |
3251 ms |
1836 KB |
Output is partially correct |
| 8 |
Partially correct |
5649 ms |
2060 KB |
Output is partially correct |
| 9 |
Partially correct |
5394 ms |
1972 KB |
Output is partially correct |
| 10 |
Partially correct |
4921 ms |
2108 KB |
Output is partially correct |
| 11 |
Partially correct |
4843 ms |
2020 KB |
Output is partially correct |
| 12 |
Partially correct |
4432 ms |
1972 KB |
Output is partially correct |
| 13 |
Partially correct |
5033 ms |
1860 KB |
Output is partially correct |
| 14 |
Partially correct |
4925 ms |
1896 KB |
Output is partially correct |
| 15 |
Partially correct |
2823 ms |
1736 KB |
Output is partially correct |
| 16 |
Partially correct |
5314 ms |
1836 KB |
Output is partially correct |
| 17 |
Incorrect |
317 ms |
200 KB |
Not correct |
| 18 |
Halted |
0 ms |
0 KB |
- |
