#include"communication.h"
#include <bits/stdc++.h>
using namespace std;
//
// --- 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
//
typedef pair<int,int> P;
void encode(int N, int x) {
vector<P> v1;
v1.push_back(P(1,N));
while (1) {
long long sum=0;
for(int i=0;i<v1.size();i++) {
//printf("%d %d\n",v1[i].first,v1[i].second);
sum+=v1[i].second-v1[i].first+1;
}
//printf(".%lld\n",sum);
if (sum<=2) {
return;
}
vector<P> cpy[3];
int ind=0;
int pr=1;
int pos=-1;
long long lv=0;
for(int i=0;i<v1.size();i++) {
if (x<=v1[i].second) {
lv+=x-v1[i].first;
break;
}
lv+=v1[i].second-v1[i].first+1;
}
long long rv=lv-sum-1;
if (lv<=sum/3) {
while (ind<v1.size()) {
if (v1[ind].second<=x) {
cpy[0].push_back(v1[ind]);
ind++;
}
else {
pr=x+1;
cpy[0].push_back(P(v1[ind].first,x));
break;
}
}
pos=0;
for(int i=1;i<3;i++) {
long long left=(sum-lv-1)/2+((sum-lv-1)%2<i-1);
while (ind<v1.size()) {
if (left==0) {
break;
}
pr=max(pr,v1[ind].first);
if (v1[ind].second-pr+1>left) {
cpy[i].push_back(P(pr,pr+left-1));
//printf("%d %d %d %d\n",i,pr,pr+left-1,left);
if (pr<=x&&x<=pr+left-1) {
pos=i;
}
pr+=left;
left=0;
break;
}
else {
cpy[i].push_back(P(pr,v1[ind].second));
//printf("%d %d %d %d\n",i,pr,v1[ind].second,left);
if (pr<=x&&x<=v1[ind].second) {
pos=i;
}
left-=v1[ind].second-pr+1;
pr=v1[ind].second+1;
ind++;
}
}
}
}
else if (rv>sum/3) {
while (ind<v1.size()) {
if (v1[ind].second<x) {
cpy[0].push_back(v1[ind]);
ind++;
}
else {
pr=x;
cpy[0].push_back(P(v1[ind].first,x-1));
break;
}
}
cpy[1].push_back(P(x,x));
pos=1;
pr=x+1;
while (ind<v1.size()) {
pr=max(pr,v1[ind].first);
if (pr<=v1[ind].second)
cpy[2].push_back(P(pr,v1[ind].second));
ind++;
}
}
else {
pos=2;
for(int i=0;i<2;i++) {
long long left=lv/2+(lv%2<i);
while (ind<v1.size()) {
if (left==0) {
break;
}
pr=max(pr,v1[ind].first);
if (v1[ind].second-pr+1>left) {
cpy[i].push_back(P(pr,pr+left-1));
//printf("%d %d %d %d\n",i,pr,pr+left-1,left);
if (pr<=x&&x<=pr+left-1) {
pos=i;
}
pr+=left;
left=0;
break;
}
else {
cpy[i].push_back(P(pr,v1[ind].second));
//printf("%d %d %d %d\n",i,pr,v1[ind].second,left);
if (pr<=x&&x<=v1[ind].second) {
pos=i;
}
left-=v1[ind].second-pr+1;
pr=v1[ind].second+1;
ind++;
}
}
}
pr=x;
while (ind<v1.size()) {
pr=max(pr,v1[ind].first);
if (pr<=v1[ind].second)
cpy[2].push_back(P(pr,v1[ind].second));
ind++;
}
}
//assert(pos!=-1);
int a[4];
if (pos==0) {
for(int i=0;i<4;i++) {
a[i]=send(0);
}
}
else if (pos==1) {
for(int i=0;i<4;i++) {
a[i]=send(1);
}
}
else {
for(int i=0;i<4;i++) {
if (i==0||i==3) {
a[i]=send(1);
}
else {
a[i]=send(0);
}
}
}
int cnt=0;
for(int i=0;i<4;i++) {
if (a[i]==1){
cnt++;
}
}
int p=-1;
if (cnt<2) {
p=1;
}
else if (cnt>2) {
p=0;
}
else {
for(int i=1;i<4;i++) {
if (a[i-1]==a[i]) {
if (a[i]==0) {
p=1;
}
else {
p=0;
}
}
}
if (p==-1) {
p=2;
}
}
vector<P>().swap(v1);
for(int i=0;i<3;i++) {
if (i!=p) {
for(int j=0;j<cpy[i].size();j++) {
v1.push_back(cpy[i][j]);
}
}
}
//break;
}
}
std::pair<int, int> decode(int N) {
vector<P> v2;
v2.push_back(P(1,N));
while (1) {
long long sum=0;
for(int i=0;i<v2.size();i++) {
sum+=v2[i].second-v2[i].first+1;
}
//printf(".%lld\n",sum);
if (sum<=2) {
vector<int> ret;
for(int i=0;i<v2.size();i++) {
for(int j=v2[i].first;j<=v2[i].second;j++) {
ret.push_back(j);
}
}
if (ret.size()==1) {
return P(ret[0],ret[0]);
}
return P(ret[0],ret[1]);
}
vector<P> cpy[3];
int ind=0;
int pr=1;
for(int i=0;i<3;i++) {
long long left=sum/3+(i<sum%3);
while (ind<v2.size()) {
if (left==0) {
break;
}
pr=max(pr,v2[ind].first);
if (v2[ind].second-pr+1>left) {
cpy[i].push_back(P(pr,pr+left-1));
pr+=left;
left=0;
break;
}
else {
cpy[i].push_back(P(pr,v2[ind].second));
left-=v2[ind].second-pr+1;
pr=v2[ind].second+1;
ind++;
}
}
}
int a[4];
int cnt=0;
for(int i=0;i<4;i++) {
a[i]=receive();
if (a[i]==1) {
cnt++;
}
}
int pos=-1;
if (cnt<2) {
pos=1;
}
else if (cnt>2) {
pos=0;
}
else {
for(int i=1;i<4;i++) {
if (a[i-1]==a[i]) {
if (a[i]==0) {
pos=1;
}
else {
pos=0;
}
}
}
if (pos==-1) {
pos=2;
}
}
vector<P>().swap(v2);
for(int i=0;i<3;i++) {
if (i!=pos) {
for(int j=0;j<cpy[i].size();j++) {
v2.push_back(cpy[i][j]);
}
}
}
}
}
Compilation message
communication.cpp: In function 'void encode(int, int)':
communication.cpp:25:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | for(int i=0;i<v1.size();i++) {
| ~^~~~~~~~~~
communication.cpp:38:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | for(int i=0;i<v1.size();i++) {
| ~^~~~~~~~~~
communication.cpp:47:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | while (ind<v1.size()) {
| ~~~^~~~~~~~~~
communication.cpp:61:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | while (ind<v1.size()) {
| ~~~^~~~~~~~~~
communication.cpp:90:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | while (ind<v1.size()) {
| ~~~^~~~~~~~~~
communication.cpp:104:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | while (ind<v1.size()) {
| ~~~^~~~~~~~~~
communication.cpp:115:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
115 | while (ind<v1.size()) {
| ~~~^~~~~~~~~~
communication.cpp:143:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
143 | while (ind<v1.size()) {
| ~~~^~~~~~~~~~
communication.cpp:203:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
203 | for(int j=0;j<cpy[i].size();j++) {
| ~^~~~~~~~~~~~~~
communication.cpp: In function 'std::pair<int, int> decode(int)':
communication.cpp:217:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
217 | for(int i=0;i<v2.size();i++) {
| ~^~~~~~~~~~
communication.cpp:223:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
223 | for(int i=0;i<v2.size();i++) {
| ~^~~~~~~~~~
communication.cpp:238:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
238 | while (ind<v2.size()) {
| ~~~^~~~~~~~~~
communication.cpp:290:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
290 | for(int j=0;j<cpy[i].size();j++) {
| ~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
200 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
302 ms |
200 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
