#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();
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
2772 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2936 KB |
Output is correct |
| 3 |
Correct |
10 ms |
2740 KB |
Output is correct |
| 4 |
Correct |
4 ms |
2740 KB |
Output is correct |
| 5 |
Correct |
11 ms |
2948 KB |
Output is correct |
| 6 |
Correct |
11 ms |
2716 KB |
Output is correct |
| 7 |
Correct |
17 ms |
2740 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
530 ms |
2828 KB |
Output is correct |
| 2 |
Correct |
287 ms |
3168 KB |
Output is correct |
| 3 |
Correct |
338 ms |
3072 KB |
Output is correct |
| 4 |
Correct |
642 ms |
3084 KB |
Output is correct |
| 5 |
Correct |
531 ms |
3160 KB |
Output is correct |
| 6 |
Correct |
443 ms |
3328 KB |
Output is correct |
| 7 |
Correct |
1724 ms |
3412 KB |
Output is correct |
| 8 |
Correct |
2565 ms |
4016 KB |
Output is correct |
| 9 |
Correct |
2399 ms |
4140 KB |
Output is correct |
| 10 |
Correct |
2398 ms |
3928 KB |
Output is correct |
| 11 |
Correct |
2237 ms |
3768 KB |
Output is correct |
| 12 |
Correct |
2425 ms |
4388 KB |
Output is correct |
| 13 |
Correct |
2252 ms |
3832 KB |
Output is correct |
| 14 |
Correct |
2248 ms |
3868 KB |
Output is correct |
| 15 |
Correct |
1189 ms |
3560 KB |
Output is correct |
| 16 |
Correct |
2543 ms |
3644 KB |
Output is correct |
| 17 |
Correct |
573 ms |
3220 KB |
Output is correct |
| 18 |
Correct |
635 ms |
3288 KB |
Output is correct |
| 19 |
Correct |
717 ms |
3216 KB |
Output is correct |
| 20 |
Correct |
603 ms |
3356 KB |
Output is correct |
| 21 |
Correct |
650 ms |
3252 KB |
Output is correct |
| 22 |
Correct |
612 ms |
3292 KB |
Output is correct |
| 23 |
Correct |
1078 ms |
3360 KB |
Output is correct |
| 24 |
Correct |
5 ms |
2740 KB |
Output is correct |
| 25 |
Correct |
8 ms |
2748 KB |
Output is correct |
| 26 |
Correct |
11 ms |
2744 KB |
Output is correct |
| 27 |
Correct |
7 ms |
2760 KB |
Output is correct |
| 28 |
Correct |
6 ms |
3008 KB |
Output is correct |
| 29 |
Correct |
14 ms |
2828 KB |
Output is correct |
| 30 |
Correct |
19 ms |
2740 KB |
Output is correct |
