#include"communication.h"
#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
vector<pair<int,int>> join(vector<pair<int,int>> v1, vector<pair<int,int>> v2) {
vector<pair<int,int>> v;
for(auto x : v1) v.pb(x);
for(auto x : v2) v.pb(x);
return v;
}
void encode(int N, int X) {
int szA = N, szB = 0;
vector<pair<int,int>> A,B;
A.pb(mp(1,N));
while(szA+szB >= 5) {
int sza = szA/2,szb = szB/2;
vector<pair<int,int>> a,b;
while(A.size() && sza != 0) {
int l = A.back().fr;
int r = A.back().sc;
A.pop_back();
int l1 = max(l,r+1-sza);
a.pb(mp(l1,r));
sza-= (r-l1+1);
if(l != l1) A.pb(mp(l,l1-1));
}
while(B.size() && szb != 0) {
int l = B.back().fr;
int r = B.back().sc;
B.pop_back();
int l1 = max(l,r+1-szb);
b.pb(mp(l1,r));
szb-= (r-l1+1);
if(l != l1) B.pb(mp(l,l1-1));
}
int ans1 = 0;
for(auto x : a) {
if(x.fr <= X && x.sc >= X) ans1 = 1;
}
for(auto x : b) {
if(x.fr <= X && x.sc >= X) ans1 = 1;
}
ans1 = send(ans1);
vector<pair<int,int>> newA, newB;
if(ans1 == 1) {
for(auto x : a) newA.pb(x);
for(auto x : b) newA.pb(x);
for(auto x : A) newB = A;
}
else {
for(auto x : A) newA.pb(x);
for(auto x : B) newA.pb(x);
for(auto x : a) newB.pb(x);
}
A = newA;
B = newB;
szA = 0;
for(auto x : A) {
szA+= x.sc-x.fr+1;
}
szB = 0;
for(auto x : B) {
szB+= x.sc-x.fr+1;
}
}
// 0000 0110 1001 1111
vector<int> pos[(1<<4)];
vector<int> masks = {0,6,9,15};
for(int i = 0; i < masks.size(); i++) {
for(int msk = 0; msk < (1<<4); msk++) {
int antw = 0;
bool ok = true;
for(int j = 0; j < 4; j++) {
if(((1<<j)&msk) == ((1<<j)&masks[i])) {
antw = 0;
}
else {
if(antw == 1) ok = false;
antw = 1;
}
}
if(ok) {
pos[msk].pb(i);
}
}
}
vector<pair<int,int>> vec,vqr;
for(auto x : A) vec.pb(x);
for(auto x : B) vec.pb(x);
int sz = szA+szB;
while(sz >= 3) {
vector<pair<int,int>> p[4];
int sz1 = sz/4; sz-= sz1;
int sz2 = sz/3; sz-= sz2;
int sz3 = sz/2; sz-= sz3;
int sz4 = sz;
while(vec.size() && sz1 != 0) {
int l = vec.back().fr;
int r = vec.back().sc;
vec.pop_back();
int l1 = max(l,r+1-sz1);
p[0].pb(mp(l1,r));
sz1-= (r-l1+1);
if(l1 != l) vec.pb(mp(l,l1-1));
}
while(vec.size() && sz2 != 0) {
int l = vec.back().fr;
int r = vec.back().sc;
vec.pop_back();
int l1 = max(l,r+1-sz2);
p[1].pb(mp(l1,r));
sz2-= (r-l1+1);
if(l1 != l) vec.pb(mp(l,l1-1));
}
while(vec.size() && sz3 != 0) {
int l = vec.back().fr;
int r = vec.back().sc;
vec.pop_back();
int l1 = max(l,r+1-sz3);
p[2].pb(mp(l1,r));
sz3-= (r-l1+1);
if(l1 != l) vec.pb(mp(l,l1-1));
}
p[3] = vec;
vec.clear();
int id0;
for(int i = 0; i < 4; i++) {
for(auto x : p[i]) {
if(x.fr <= X && x.sc >= X) id0 = i;
}
}
int msksend = 0;
for(int i = 3; i >= 0; i--) {
msksend+= (1<<i)*send(((1<<i)&masks[id0]) != 0);
}
int id1;
for(auto x : pos[msksend]) {
if(x != id0) id1 = x;
}
for(int i = 0; i < 4; i++) {
if(i != id0 && i != id1) p[i].clear();
}
vec.clear();
for(auto x : p[0]) vec.pb(x);
for(auto x : p[1]) vec.pb(x);
for(auto x : p[2]) vec.pb(x);
for(auto x : p[3]) vec.pb(x);
sz = 0;
for(auto x : vec) sz+= x.sc-x.fr+1;
}
vector<pair<int,int>> vc1;
for(auto x : vec) {
for(int i = x.fr; i <= x.sc; i++) vc1.pb(mp(i,i));
}
vec = vc1;
}
std::pair<int, int> decode(int N) {
int szA = N, szB = 0;
vector<pair<int,int>> A,B;
A.pb(mp(1,N));
while(szA+szB >= 5) {
int sza = szA/2,szb = szB/2;
vector<pair<int,int>> a,b;
while(A.size() && sza != 0) {
int l = A.back().fr;
int r = A.back().sc;
A.pop_back();
int l1 = max(l,r+1-sza);
a.pb(mp(l1,r));
sza-= (r-l1+1);
if(l != l1) A.pb(mp(l,l1-1));
}
while(B.size() && szb != 0) {
int l = B.back().fr;
int r = B.back().sc;
B.pop_back();
int l1 = max(l,r+1-szb);
b.pb(mp(l1,r));
szb-= (r-l1+1);
if(l != l1) B.pb(mp(l,l1-1));
}
int ans1 = receive();
vector<pair<int,int>> newA, newB;
if(ans1 == 1) {
for(auto x : a) newA.pb(x);
for(auto x : b) newA.pb(x);
for(auto x : A) newB = A;
}
else {
for(auto x : A) newA.pb(x);
for(auto x : B) newA.pb(x);
for(auto x : a) newB.pb(x);
}
A = newA;
B = newB;
szA = 0;
for(auto x : A) {
szA+= x.sc-x.fr+1;
}
szB = 0;
for(auto x : B) {
szB+= x.sc-x.fr+1;
}
}
// 0000 0110 1001 1111
vector<int> pos[(1<<4)];
vector<int> masks = {0,6,9,15};
for(int i = 0; i < masks.size(); i++) {
for(int msk = 0; msk < (1<<4); msk++) {
int antw = 0;
bool ok = true;
for(int j = 0; j < 4; j++) {
if(((1<<j)&msk) == ((1<<j)&masks[i])) {
antw = 0;
}
else {
if(antw == 1) ok = false;
antw = 1;
}
}
if(ok) {
pos[msk].pb(i);
}
}
}
vector<pair<int,int>> vec,vqr;
for(auto x : A) vec.pb(x);
for(auto x : B) vec.pb(x);
int sz = szA+szB;
while(sz >= 3) {
vector<pair<int,int>> p[4];
int sz1 = sz/4; sz-= sz1;
int sz2 = sz/3; sz-= sz2;
int sz3 = sz/2; sz-= sz3;
int sz4 = sz;
while(vec.size() && sz1 != 0) {
int l = vec.back().fr;
int r = vec.back().sc;
vec.pop_back();
int l1 = max(l,r+1-sz1);
p[0].pb(mp(l1,r));
sz1-= (r-l1+1);
if(l1 != l) vec.pb(mp(l,l1-1));
}
while(vec.size() && sz2 != 0) {
int l = vec.back().fr;
int r = vec.back().sc;
vec.pop_back();
int l1 = max(l,r+1-sz2);
p[1].pb(mp(l1,r));
sz2-= (r-l1+1);
if(l1 != l) vec.pb(mp(l,l1-1));
}
while(vec.size() && sz3 != 0) {
int l = vec.back().fr;
int r = vec.back().sc;
vec.pop_back();
int l1 = max(l,r+1-sz3);
p[2].pb(mp(l1,r));
sz3-= (r-l1+1);
if(l1 != l) vec.pb(mp(l,l1-1));
}
p[3] = vec;
vec.clear();
int msksend = 0;
for(int i = 3; i >= 0; i--) {
msksend+= (1<<i)*receive();
}
int id0,id1;
for(auto x : pos[msksend]) {
id0 = x;
}
for(auto x : pos[msksend]) {
if(x != id0) id1 = x;
}
for(int i = 0; i < 4; i++) {
if(i != id0 && i != id1) p[i].clear();
}
vec.clear();
for(auto x : p[0]) vec.pb(x);
for(auto x : p[1]) vec.pb(x);
for(auto x : p[2]) vec.pb(x);
for(auto x : p[3]) vec.pb(x);
sz = 0;
for(auto x : vec) sz+= x.sc-x.fr+1;
}
vector<pair<int,int>> vc1;
for(auto x : vec) {
for(int i = x.fr; i <= x.sc; i++) vc1.pb(mp(i,i));
}
vec = vc1;
if(vec.size() == 1) return {vec[0].fr,vec[0].fr};
else return {vec[0].fr,vec[1].fr};
}
Compilation message
communication.cpp: In function 'void encode(int, int)':
communication.cpp:60:22: warning: variable 'x' set but not used [-Wunused-but-set-variable]
60 | for(auto x : A) newB = A;
| ^
communication.cpp:83:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | for(int i = 0; i < masks.size(); i++) {
| ~~^~~~~~~~~~~~~~
communication.cpp:112:13: warning: unused variable 'sz4' [-Wunused-variable]
112 | int sz4 = sz;
| ^~~
communication.cpp: In function 'std::pair<int, int> decode(int)':
communication.cpp:210:22: warning: variable 'x' set but not used [-Wunused-but-set-variable]
210 | for(auto x : A) newB = A;
| ^
communication.cpp:233:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
233 | for(int i = 0; i < masks.size(); i++) {
| ~~^~~~~~~~~~~~~~
communication.cpp:262:13: warning: unused variable 'sz4' [-Wunused-variable]
262 | int sz4 = sz;
| ^~~
communication.cpp: In function 'void encode(int, int)':
communication.cpp:160:30: warning: 'id1' may be used uninitialized in this function [-Wmaybe-uninitialized]
160 | if(i != id0 && i != id1) p[i].clear();
| ~~^~~~~~
communication.cpp:160:18: warning: 'id0' may be used uninitialized in this function [-Wmaybe-uninitialized]
160 | if(i != id0 && i != id1) p[i].clear();
| ~~^~~~~~
communication.cpp: In function 'std::pair<int, int> decode(int)':
communication.cpp:306:30: warning: 'id1' may be used uninitialized in this function [-Wmaybe-uninitialized]
306 | if(i != id0 && i != id1) p[i].clear();
| ~~^~~~~~
communication.cpp:306:18: warning: 'id0' may be used uninitialized in this function [-Wmaybe-uninitialized]
306 | if(i != id0 && i != id1) p[i].clear();
| ~~^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
1784 KB |
Output is correct |
| 2 |
Correct |
6 ms |
1704 KB |
Output is correct |
| 3 |
Correct |
9 ms |
1680 KB |
Output is correct |
| 4 |
Correct |
12 ms |
1660 KB |
Output is correct |
| 5 |
Correct |
15 ms |
1736 KB |
Output is correct |
| 6 |
Correct |
27 ms |
1744 KB |
Output is correct |
| 7 |
Correct |
47 ms |
1676 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
705 ms |
1736 KB |
Output is correct |
| 2 |
Correct |
356 ms |
1800 KB |
Output is correct |
| 3 |
Correct |
450 ms |
1804 KB |
Output is correct |
| 4 |
Correct |
835 ms |
1804 KB |
Output is correct |
| 5 |
Correct |
635 ms |
1780 KB |
Output is correct |
| 6 |
Correct |
366 ms |
1668 KB |
Output is correct |
| 7 |
Correct |
1895 ms |
2044 KB |
Output is correct |
| 8 |
Correct |
2965 ms |
2200 KB |
Output is correct |
| 9 |
Correct |
2721 ms |
2044 KB |
Output is correct |
| 10 |
Correct |
2847 ms |
2056 KB |
Output is correct |
| 11 |
Correct |
2610 ms |
2048 KB |
Output is correct |
| 12 |
Correct |
2735 ms |
2352 KB |
Output is correct |
| 13 |
Correct |
2622 ms |
2088 KB |
Output is correct |
| 14 |
Correct |
2607 ms |
2064 KB |
Output is correct |
| 15 |
Correct |
1418 ms |
1816 KB |
Output is correct |
| 16 |
Correct |
2822 ms |
1960 KB |
Output is correct |
| 17 |
Correct |
795 ms |
1752 KB |
Output is correct |
| 18 |
Correct |
742 ms |
1924 KB |
Output is correct |
| 19 |
Correct |
841 ms |
1804 KB |
Output is correct |
| 20 |
Correct |
885 ms |
1892 KB |
Output is correct |
| 21 |
Correct |
716 ms |
2124 KB |
Output is correct |
| 22 |
Correct |
852 ms |
1840 KB |
Output is correct |
| 23 |
Correct |
1126 ms |
1864 KB |
Output is correct |
| 24 |
Correct |
15 ms |
1752 KB |
Output is correct |
| 25 |
Correct |
15 ms |
1724 KB |
Output is correct |
| 26 |
Correct |
15 ms |
1776 KB |
Output is correct |
| 27 |
Correct |
7 ms |
1684 KB |
Output is correct |
| 28 |
Correct |
14 ms |
1712 KB |
Output is correct |
| 29 |
Correct |
23 ms |
1764 KB |
Output is correct |
| 30 |
Correct |
28 ms |
1680 KB |
Output is correct |
