#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;
vector<P> v1;
vector<P> v2;
void encode(int N, int x) {
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;
for(int i=0;i<3;i++) {
long long left=sum/3+(i<sum%3);
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++;
}
}
}
int a[4];
assert(pos!=-1);
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]);
}
}
}
}
}
std::pair<int, int> decode(int N) {
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:26: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]
26 | for(int i=0;i<v1.size();i++) {
| ~^~~~~~~~~~
communication.cpp:40: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]
40 | while (ind<v1.size()) {
| ~~~^~~~~~~~~~
communication.cpp:120: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]
120 | for(int j=0;j<cpy[i].size();j++) {
| ~^~~~~~~~~~~~~~
communication.cpp: In function 'std::pair<int, int> decode(int)':
communication.cpp:132: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]
132 | for(int i=0;i<v2.size();i++) {
| ~^~~~~~~~~~
communication.cpp:138: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]
138 | for(int i=0;i<v2.size();i++) {
| ~^~~~~~~~~~
communication.cpp:153: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]
153 | while (ind<v2.size()) {
| ~~~^~~~~~~~~~
communication.cpp:205: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]
205 | for(int j=0;j<cpy[i].size();j++) {
| ~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
328 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
416 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
