#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;
}
}
assert(false);
}
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> ans;
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) ans.eb(num[0]);
else if(tmp == 0b0110) ans.eb(num[1]);
else if(tmp == 0b1001) ans.eb(num[2]);
}
while(ans.size() < 2) ans.eb(num[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 |
Incorrect |
27 ms |
208 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
389 ms |
200 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
