#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;
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++;
}
}
}
//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:39: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]
39 | while (ind<v1.size()) {
| ~~~^~~~~~~~~~
communication.cpp:119: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]
119 | for(int j=0;j<cpy[i].size();j++) {
| ~^~~~~~~~~~~~~~
communication.cpp: In function 'std::pair<int, int> decode(int)':
communication.cpp:133: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]
133 | for(int i=0;i<v2.size();i++) {
| ~^~~~~~~~~~
communication.cpp:139: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]
139 | for(int i=0;i<v2.size();i++) {
| ~^~~~~~~~~~
communication.cpp:154: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]
154 | while (ind<v2.size()) {
| ~~~^~~~~~~~~~
communication.cpp:206: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]
206 | for(int j=0;j<cpy[i].size();j++) {
| ~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
1724 KB |
Output is correct |
| 2 |
Correct |
11 ms |
1776 KB |
Output is correct |
| 3 |
Correct |
15 ms |
1884 KB |
Output is correct |
| 4 |
Correct |
12 ms |
1732 KB |
Output is correct |
| 5 |
Correct |
10 ms |
1788 KB |
Output is correct |
| 6 |
Correct |
22 ms |
1812 KB |
Output is correct |
| 7 |
Correct |
42 ms |
1704 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
1234 ms |
1760 KB |
Output is partially correct |
| 2 |
Partially correct |
741 ms |
1736 KB |
Output is partially correct |
| 3 |
Partially correct |
645 ms |
1720 KB |
Output is partially correct |
| 4 |
Partially correct |
1206 ms |
1784 KB |
Output is partially correct |
| 5 |
Partially correct |
1225 ms |
1740 KB |
Output is partially correct |
| 6 |
Partially correct |
1081 ms |
1664 KB |
Output is partially correct |
| 7 |
Partially correct |
3945 ms |
1760 KB |
Output is partially correct |
| 8 |
Partially correct |
6777 ms |
1928 KB |
Output is partially correct |
| 9 |
Partially correct |
6924 ms |
1804 KB |
Output is partially correct |
| 10 |
Partially correct |
6160 ms |
1904 KB |
Output is partially correct |
| 11 |
Partially correct |
6671 ms |
1956 KB |
Output is partially correct |
| 12 |
Partially correct |
6945 ms |
1872 KB |
Output is partially correct |
| 13 |
Partially correct |
6977 ms |
1900 KB |
Output is partially correct |
| 14 |
Partially correct |
6921 ms |
1988 KB |
Output is partially correct |
| 15 |
Partially correct |
3422 ms |
1872 KB |
Output is partially correct |
| 16 |
Partially correct |
7191 ms |
1816 KB |
Output is partially correct |
| 17 |
Partially correct |
1562 ms |
2036 KB |
Output is partially correct |
| 18 |
Partially correct |
1675 ms |
1816 KB |
Output is partially correct |
| 19 |
Partially correct |
1637 ms |
1840 KB |
Output is partially correct |
| 20 |
Partially correct |
1683 ms |
1832 KB |
Output is partially correct |
| 21 |
Partially correct |
1744 ms |
1736 KB |
Output is partially correct |
| 22 |
Partially correct |
1621 ms |
1728 KB |
Output is partially correct |
| 23 |
Partially correct |
2666 ms |
1852 KB |
Output is partially correct |
| 24 |
Correct |
7 ms |
1696 KB |
Output is correct |
| 25 |
Correct |
11 ms |
1800 KB |
Output is correct |
| 26 |
Correct |
19 ms |
1704 KB |
Output is correct |
| 27 |
Correct |
8 ms |
1636 KB |
Output is correct |
| 28 |
Correct |
11 ms |
1688 KB |
Output is correct |
| 29 |
Correct |
26 ms |
1808 KB |
Output is correct |
| 30 |
Correct |
42 ms |
1720 KB |
Output is correct |
