#include"communication.h"
#include <bits/stdc++.h>
using namespace std;
struct Range {
int l, r;
Range(int l, int r) : l(l), r(r) {}
int size() { return r - l + 1; }
pair<Range, Range> split(int qtd) {
return {Range(l, l + qtd - 1), Range(l + qtd, r) };
}
friend ostream& operator<<(ostream& os, const Range& r) {
return os << '<' <<r.l << ", " << r.r << '>';
}
};
int get_total_size(vector<Range> ranges) {
int ans = 0;
for(Range r : ranges)
ans += r.size();
return ans;
}
pair<vector<Range>, vector<Range>> split(vector<Range> ranges) {
int sz = get_total_size(ranges);
vector<Range> g[2];
int now = 0;
for(Range r : ranges) {
if(now + r.size() <= (sz+1)/2)
g[0].push_back(r), now += r.size();
else if(now < (sz+1)/2) {
auto [r1, r2] = r.split((sz+1)/2 - now);
g[0].push_back(r1);
g[1].push_back(r2);
now = (sz+1)/2;
} else
g[1].push_back(r);
}
return {g[0], g[1]};
}
pair<int,int> answer(vector<Range> ranges) {
vector<int> ans;
for(Range r : ranges)
for(int i = r.l; i <= r.r; i++)
ans.push_back(i);
return {ans[0], ans[1]};
}
pair<int,int> build_decode(vector<Range> head, vector<Range> left, vector<Range> right) {
if(get_total_size(head) <= 2 && !get_total_size(left) && !get_total_size(right))
return answer(head);
if(get_total_size(head) <= 1 && get_total_size(left) <= 1 && get_total_size(right) <= 1) {
if(receive())
return {head[0].l, left[0].l};
else
return {head[0].l, right[0].l};
}
if(get_total_size(head) <= 2 && get_total_size(left) <= 1 && !get_total_size(right)) {
if(receive() == 1)
return answer(head);
if(receive() == 0)
return {head[0].l, left[0].l};
else if(head.size() == 2)
return {head[1].l, left[0].l};
else
return {head[0].r, left[0].l};
}
// assumes there is always the same number of people on the left and right
int n = (int)head.size();
vector<Range> g[2];
pair<vector<Range>, vector<Range>> spl = split(head);
g[0] = spl.first;
g[1] = spl.second;
if(get_total_size(left) > get_total_size(right))
swap(g[0], g[1]);
int k = receive();
vector<Range> &pre = k ? right : left;
spl = split(g[!k]);
int m = g[!k].size();
vector<Range> f1 = spl.first;
vector<Range> f2 = spl.second;
g[k].insert(g[k].end(), pre.begin(), pre.end());
return build_decode(g[k], f1, f2);
}
bool in(vector<Range> ranges, int x) {
for(Range r : ranges)
if(r.l <= x && x <= r.r)
return true;
return false;
}
void build_encode(vector<Range> head, vector<Range> left, vector<Range> right, int secret) {
if(get_total_size(head) <= 2 && !get_total_size(left) && !get_total_size(right))
return;
if(get_total_size(head) <= 1 && get_total_size(left) <= 1 && get_total_size(right) <= 1) {
if(in(left, secret))
send(0);
else // se tiver em left ou right signifca que deu errado antes entao to garantido
send(1); // se tiver em head nao importa
return;
}
if(get_total_size(head) <= 2 && get_total_size(left) <= 1 && !get_total_size(right)) {
if(in(left, secret)) {
send(0), send(0); // so importa que vou pra esquerda agr, dps fds
return;
} else {
int nxt = send(1);
if(nxt) return; // fui pra direita entao ja posso terminar
if(head[0].l == secret)
send(0);
else
send(1);
return;
}
}
// assumes there is always the same number of people on the left and right
int n = (int)head.size();
vector<Range> g[2];
pair<vector<Range>, vector<Range>> spl = split(head);
g[0] = spl.first;
g[1] = spl.second;
if(get_total_size(left) > get_total_size(right))
swap(g[0], g[1]);
int k;
if(in(left, secret)) {
k = 0;
send(0); // anterior foi mudado entao garanto movimento aqui
} else if(in(right, secret)) {
k = 1;
send(1); // anterior foi mudado entao garanto movimento aqui
} else {
int tento = in(g[1], secret);
k = send(tento); // tento ir pra aquele lado mas se nao for tenho que mover pro outro
}
vector<Range> &pre = k ? right : left;
spl = split(g[!k]);
int m = g[!k].size();
vector<Range> f1 = spl.first;
vector<Range> f2 = spl.second;
g[k].insert(g[k].end(), pre.begin(), pre.end());
build_encode(g[k], f1, f2, secret);
}
void encode(int N, int X) {
vector<Range> a = {Range(1, N)};
vector<int> s;
return build_encode(a, {}, {}, X);
}
std::pair<int, int> decode(int N) {
vector<Range> a = {Range(1, N)};
vector<int> s;
return build_decode(a, {}, {});
}
Compilation message
communication.cpp: In function 'std::pair<int, int> build_decode(std::vector<Range>, std::vector<Range>, std::vector<Range>)':
communication.cpp:76:6: warning: unused variable 'n' [-Wunused-variable]
76 | int n = (int)head.size();
| ^
communication.cpp:89:6: warning: unused variable 'm' [-Wunused-variable]
89 | int m = g[!k].size();
| ^
communication.cpp: In function 'void build_encode(std::vector<Range>, std::vector<Range>, std::vector<Range>, int)':
communication.cpp:134:6: warning: unused variable 'n' [-Wunused-variable]
134 | int n = (int)head.size();
| ^
communication.cpp:158:6: warning: unused variable 'm' [-Wunused-variable]
158 | int m = g[!k].size();
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
516 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
546 ms |
3556 KB |
Output is correct |
| 2 |
Correct |
292 ms |
3236 KB |
Output is correct |
| 3 |
Correct |
325 ms |
2948 KB |
Output is correct |
| 4 |
Correct |
554 ms |
3124 KB |
Output is correct |
| 5 |
Correct |
464 ms |
3332 KB |
Output is correct |
| 6 |
Correct |
441 ms |
3048 KB |
Output is correct |
| 7 |
Correct |
1752 ms |
3244 KB |
Output is correct |
| 8 |
Correct |
2647 ms |
4176 KB |
Output is correct |
| 9 |
Correct |
2324 ms |
3844 KB |
Output is correct |
| 10 |
Correct |
2260 ms |
3928 KB |
Output is correct |
| 11 |
Correct |
2378 ms |
3556 KB |
Output is correct |
| 12 |
Correct |
2352 ms |
3716 KB |
Output is correct |
| 13 |
Correct |
2367 ms |
3712 KB |
Output is correct |
| 14 |
Correct |
2299 ms |
4000 KB |
Output is correct |
| 15 |
Correct |
1161 ms |
3420 KB |
Output is correct |
| 16 |
Correct |
2468 ms |
3616 KB |
Output is correct |
| 17 |
Correct |
591 ms |
3308 KB |
Output is correct |
| 18 |
Correct |
605 ms |
3356 KB |
Output is correct |
| 19 |
Correct |
578 ms |
3116 KB |
Output is correct |
| 20 |
Correct |
576 ms |
3668 KB |
Output is correct |
| 21 |
Correct |
637 ms |
3464 KB |
Output is correct |
| 22 |
Correct |
647 ms |
3572 KB |
Output is correct |
| 23 |
Correct |
1070 ms |
3548 KB |
Output is correct |
| 24 |
Incorrect |
2 ms |
332 KB |
Not correct |
| 25 |
Halted |
0 ms |
0 KB |
- |
