#include"communication.h"
#include <bits/stdc++.h>
#define iter(a) a.begin(), a.end()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(iter(a), greater<>())
#define eb emplace_back
#define ef emplace_front
#define pob pop_back()
#define pof pop_front()
#define mp make_pair
#define F first
#define S second
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define printv(a, b) { \
for(auto pv : a) b << pv << " "; \
b << "\n"; \
}
using namespace std;
typedef long long ll;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
return o << '(' << p.F << ',' << p.S << ')';
}
const int SZ = 4;
struct Node{
vector<pii> a, b;
int sizea(){
int sum = 0;
for(pii i : a) sum += i.S - i.F + 1;
return sum;
}
int sizeb(){
int sum = 0;
for(pii i : b) sum += i.S - i.F + 1;
return sum;
}
int size(){
return sizea() + sizeb();
}
bool ina(int v){
for(pii i : a){
if(i.F <= v && v <= i.S) return true;
}
return false;
}
bool inb(int v){
for(pii i : b){
if(i.F <= v && v <= i.S) return true;
}
return false;
}
vector<int> num(){
vector<int> ans;
for(pii i : a){
for(int j = i.F; j <= i.S; j++) ans.eb(j);
}
for(pii i : b){
for(int j = i.F; j <= i.S; j++) ans.eb(j);
}
return ans;
}
};
pair<Node, Node> split(Node v){
Node ln, rn;
int len = v.sizea();
int now = 0;
int ls = (len + 1) / 2;
for(pii i : v.a){
if(now + i.S - i.F + 1 <= ls){
ln.a.eb(i);
rn.b.eb(i);
now += i.S - i.F + 1;
continue;
}
if(now >= ls){
rn.a.eb(i);
ln.b.eb(i);
continue;
}
int tmp = ls - now;
now = ls;
ln.a.eb(mp(i.F, i.F + tmp - 1));
rn.b.eb(mp(i.F, i.F + tmp - 1));
rn.a.eb(mp(i.F + tmp, i.S));
ln.b.eb(mp(i.F + tmp, i.S));
}
len = v.sizeb();
now = 0;
ls = len / 2;
for(pii i : v.b){
if(now + i.S - i.F + 1 <= ls){
ln.a.eb(i);
now += i.S - i.F + 1;
continue;
}
if(now >= ls){
rn.a.eb(i);
continue;
}
int tmp = ls - now;
now = ls;
ln.a.eb(mp(i.F, i.F + tmp - 1));
rn.a.eb(mp(i.F + tmp, i.S));
}
/*cerr << "split " << v.sizea() << " " << v.sizeb() << "\n";
cerr << " left " << ln.sizea() << " " << ln.sizeb() << "\n";
cerr << " right " << rn.sizea() << " " << rn.sizeb() << "\n";*/
return mp(ln, rn);
}
void sendnum(int v){
for(int i = 0; i < 4; i++){
if(1 << i & v) send(1);
else send(0);
}
}
int readnum(){
int v = 0;
for(int i = 0; i < 4; i++){
if(receive()) v |= 1 << i;
}
return v;
}
void encode(int N, int X) {
Node now;
now.a.eb(mp(1, 1000000000));
while(now.size() > 3){
Node l, r;
tie(l, r) = split(now);
int nxt;
if(l.ina(X)) nxt = 0;
else nxt = 1;
nxt = send(nxt);
if(nxt == 0) now = l;
else now = r;
}
vector<int> num = now.num();
vector<int> owo = {0b0000, 0b0110, 0b1001};
for(int i = 0; i < num.size(); i++){
if(X == num[i]){
sendnum(owo[i]);
return;
}
}
}
pii decode(int N) {
Node now;
now.a.eb(mp(1, 1000000000));
while(now.size() > 3){
Node l, r;
tie(l, r) = split(now);
int nxt = receive();
if(nxt == 0) now = l;
else now = r;
}
vector<int> num = now.num();
while(num.size() < 3) num.eb(1);
int X = readnum();
vector<int> tans;
for(int i = 0; i < (1 << 4); i++){
bool ok = true;
for(int j = 0; j + 1 < SZ; j++){
if((1 << j & i) && (1 << (j + 1) & i)) ok = false;
}
if(!ok) continue;
int tmp = X ^ i;
if(tmp == 0b0000) tans.eb(num[0]);
else if(tmp == 0b0110) tans.eb(num[1]);
else if(tmp == 0b1001) tans.eb(num[2]);
}
vector<int> ans;
for(int i : tans){
if(i <= N) ans.eb(i);
}
while(ans.size() < 2) ans.eb(ans[0]);
return mp(ans[0], ans[1]);
}
Compilation message
communication.cpp: In function 'void encode(int, int)':
communication.cpp:160:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
160 | for(int i = 0; i < num.size(); i++){
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
110 ms |
1724 KB |
Output is correct |
| 2 |
Correct |
129 ms |
1716 KB |
Output is correct |
| 3 |
Correct |
168 ms |
1832 KB |
Output is correct |
| 4 |
Correct |
96 ms |
1728 KB |
Output is correct |
| 5 |
Correct |
114 ms |
1668 KB |
Output is correct |
| 6 |
Correct |
339 ms |
1736 KB |
Output is correct |
| 7 |
Correct |
794 ms |
1748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
817 ms |
1716 KB |
Output is correct |
| 2 |
Correct |
335 ms |
1680 KB |
Output is correct |
| 3 |
Correct |
542 ms |
1752 KB |
Output is correct |
| 4 |
Correct |
673 ms |
1744 KB |
Output is correct |
| 5 |
Correct |
557 ms |
1796 KB |
Output is correct |
| 6 |
Correct |
665 ms |
1788 KB |
Output is correct |
| 7 |
Correct |
2135 ms |
1952 KB |
Output is correct |
| 8 |
Correct |
3497 ms |
1868 KB |
Output is correct |
| 9 |
Correct |
3354 ms |
2028 KB |
Output is correct |
| 10 |
Correct |
3406 ms |
1976 KB |
Output is correct |
| 11 |
Correct |
3299 ms |
1820 KB |
Output is correct |
| 12 |
Correct |
3177 ms |
1868 KB |
Output is correct |
| 13 |
Correct |
2950 ms |
2032 KB |
Output is correct |
| 14 |
Correct |
3052 ms |
2152 KB |
Output is correct |
| 15 |
Correct |
1477 ms |
1840 KB |
Output is correct |
| 16 |
Correct |
3519 ms |
1960 KB |
Output is correct |
| 17 |
Correct |
798 ms |
1872 KB |
Output is correct |
| 18 |
Correct |
837 ms |
1748 KB |
Output is correct |
| 19 |
Correct |
794 ms |
1788 KB |
Output is correct |
| 20 |
Correct |
780 ms |
1752 KB |
Output is correct |
| 21 |
Correct |
779 ms |
1876 KB |
Output is correct |
| 22 |
Correct |
818 ms |
1756 KB |
Output is correct |
| 23 |
Correct |
1454 ms |
1788 KB |
Output is correct |
| 24 |
Correct |
103 ms |
1664 KB |
Output is correct |
| 25 |
Correct |
128 ms |
1720 KB |
Output is correct |
| 26 |
Correct |
167 ms |
1776 KB |
Output is correct |
| 27 |
Correct |
103 ms |
1688 KB |
Output is correct |
| 28 |
Correct |
99 ms |
1604 KB |
Output is correct |
| 29 |
Correct |
332 ms |
1824 KB |
Output is correct |
| 30 |
Correct |
552 ms |
1796 KB |
Output is correct |
