#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 > 5)
{
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[v];
X = nx;
lim = nlim;
}
long long v = 125;
int arr[5][10];
int i;
for (i = 0; i < 5; i++)
{
int j;
for (j = 0; j < 10; j++)
{
v *= 1272;
v += 125792;
v %= 12592043;
arr[i][j] = !(v & (1 << 16));
}
}
for (i = 0; i < 10; 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 < 5; i++)
{
int j;
for (j = 0; j < 10; j++)
{
v *= 1272;
v += 125792;
v %= 12592043;
arr[i][j] = !(v & (1 << 16));
}
}
int lim = 1000000002;
vector<int>lims;
vector<int>vs;
while (lim > 5)
{
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];
}
lim = dp[v];
}
vector<int>r;
for (i = 0; i < 124; i++)
{
r.push_back(receive());
}
vector<int>st;
for (i = 0; i < 5; i++)
{
int bef = 0;
int j;
for (j = 0; j < 10; j++)
{
if (bef && (r[j + 114] != arr[i][j]))
break;
bef = r[j + 114] != arr[i][j];
}
if (j == 10)
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 = 114;
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:17: 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:10: 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:131:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
131 | for (i = 0; i < st.size(); i++)
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
53 ms |
200 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
412 ms |
200 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
