#include "communication.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> merge_vec(vector<pair<int, int>> x, vector<pair<int, int>> y) {
int sz_x = x.size();
int sz_y = y.size();
int i = 0, j = 0;
vector<pair<int, int>> res;
while (i < sz_x || j < sz_y) {
if (j == sz_y || (i < sz_x && x[i].first < y[j].first)) {
if (res.empty() || res.back().second != x[i].first - 1) {
res.push_back(x[i]);
} else {
res.back().second = x[i].second;
}
i++;
} else {
if (res.empty() || res.back().second != y[j].first - 1) {
res.push_back(y[j]);
} else {
res.back().second = y[j].second;
}
j++;
}
}
return res;
}
struct state {
vector<pair<int, int>> interval;
int len;
state(int N) {
if (N == -1) {
len = 0;
interval = {};
} else {
len = N;
interval = {make_pair(1, N)};
}
}
void add(pair<int, int> p) {
interval = merge_vec(interval, {p});
len += p.second - p.first + 1;
}
bool in(int x) {
for (auto& p : interval) {
if (p.first <= x && x <= p.second) {
return true;
}
}
return false;
}
pair<state, state> split(int delta) {
state L(-1);
state R(-1);
if (len == 0) {
return {L, R};
}
for (auto& p : interval) {
if (L.len + p.second - p.first + 1 <= (len + delta) / 2) {
L.add(p);
} else if (L.len >= (len + delta) / 2) {
R.add(p);
} else {
L.add({p.first, p.first + (len + delta) / 2 - L.len - 1});
assert(!L.interval.empty());
R.add({L.interval.back().second + 1, p.second});
}
}
return {L, R};
}
vector<int> all() {
vector<int> v;
for (auto& p : interval) {
for (int i = p.first; i <= p.second; i++) {
v.push_back(i);
}
}
return v;
}
};
state Merge(state p, state q) {
state ret(-1);
ret.interval = merge_vec(p.interval, q.interval);
ret.len = p.len + q.len;
return ret;
}
pair<int, int> solve(int N, int X) {
state good(N);
state bad(-1);
while (good.len + bad.len > 3) {
auto good_split = good.split(0);
state good_L = good_split.first;
state good_R = good_split.second;
auto bad_split = bad.split(1);
state bad_L = bad_split.first;
state bad_R = bad_split.second;
// cout << "good_L = ";
// for (auto& p : good_L.interval) {
// cout << p.first << " " << p.second << '\n';
// }
// cout << '\n';
// cout << "good_R = ";
// for (auto& p : good_R.interval) {
// cout << p.first << " " << p.second << '\n';
// }
// cout << '\n';
// cout << "bad_L = ";
// for (auto& p : bad_L.interval) {
// cout << p.first << " " << p.second << '\n';
// }
// cout << '\n';
// cout << "bad_R = ";
// for (auto& p : bad_R.interval) {
// cout << p.first << " " << p.second << '\n';
// }
// cout << '\n';
int f;
if (X == -1) {
f = receive();
} else {
f = send(good_L.in(X) || bad_L.in(X));
}
if (f == 0) {
good = Merge(good_R, bad_R);
bad = good_L;
} else {
good = Merge(good_L, bad_L);
bad = good_R;
}
}
vector<int> nums = Merge(good, bad).all();
if (nums.size() == 3) {
if (X != -1) {
if (nums[0] == X) {
send(0);
send(0);
send(0);
send(0);
}
if (nums[1] == X) {
send(0);
send(1);
send(1);
send(0);
}
if (nums[2] == X) {
send(1);
send(1);
send(1);
send(1);
}
} else {
vector<vector<int>> f;
f.push_back({0, 0, 0, 0});
f.push_back({0, 1, 1, 0});
f.push_back({1, 1, 1, 1});
vector<int> seq;
seq.push_back(receive());
seq.push_back(receive());
seq.push_back(receive());
seq.push_back(receive());
vector<int> new_nums;
for (int i = 0; i < 3; i++) {
bool ok = true;
for (int j = 1; j < 4; j++) {
if (seq[j] != f[i][j] && seq[j - 1] != f[i][j - 1]) {
ok = false;
}
}
if (ok) {
new_nums.push_back(nums[i]);
}
}
swap(new_nums, nums);
}
}
if (nums.size() == 1) {
return {nums[0], nums[0]};
}
return {nums[0], nums[1]};
}
void encode(int N, int X) {
solve(N, X);
}
pair<int, int> decode(int N) {
return solve(N, -1);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
1688 KB |
Output is correct |
| 2 |
Correct |
9 ms |
1740 KB |
Output is correct |
| 3 |
Correct |
14 ms |
1780 KB |
Output is correct |
| 4 |
Correct |
11 ms |
1760 KB |
Output is correct |
| 5 |
Correct |
15 ms |
1684 KB |
Output is correct |
| 6 |
Correct |
26 ms |
1892 KB |
Output is correct |
| 7 |
Correct |
48 ms |
1740 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
725 ms |
1728 KB |
Output is correct |
| 2 |
Correct |
400 ms |
1724 KB |
Output is correct |
| 3 |
Correct |
484 ms |
1900 KB |
Output is correct |
| 4 |
Correct |
772 ms |
1724 KB |
Output is correct |
| 5 |
Correct |
702 ms |
1740 KB |
Output is correct |
| 6 |
Correct |
695 ms |
1688 KB |
Output is correct |
| 7 |
Correct |
2651 ms |
1964 KB |
Output is correct |
| 8 |
Correct |
3499 ms |
2080 KB |
Output is correct |
| 9 |
Correct |
3405 ms |
2112 KB |
Output is correct |
| 10 |
Correct |
3273 ms |
2084 KB |
Output is correct |
| 11 |
Correct |
3792 ms |
2032 KB |
Output is correct |
| 12 |
Correct |
3411 ms |
1952 KB |
Output is correct |
| 13 |
Correct |
3191 ms |
2072 KB |
Output is correct |
| 14 |
Correct |
3315 ms |
1944 KB |
Output is correct |
| 15 |
Correct |
1725 ms |
1900 KB |
Output is correct |
| 16 |
Correct |
3857 ms |
1880 KB |
Output is correct |
| 17 |
Correct |
974 ms |
1876 KB |
Output is correct |
| 18 |
Correct |
999 ms |
1884 KB |
Output is correct |
| 19 |
Correct |
1078 ms |
1744 KB |
Output is correct |
| 20 |
Correct |
975 ms |
1796 KB |
Output is correct |
| 21 |
Correct |
954 ms |
1824 KB |
Output is correct |
| 22 |
Correct |
1175 ms |
1996 KB |
Output is correct |
| 23 |
Correct |
1739 ms |
1912 KB |
Output is correct |
| 24 |
Correct |
9 ms |
1680 KB |
Output is correct |
| 25 |
Correct |
18 ms |
1684 KB |
Output is correct |
| 26 |
Correct |
21 ms |
1688 KB |
Output is correct |
| 27 |
Correct |
12 ms |
1844 KB |
Output is correct |
| 28 |
Correct |
12 ms |
1764 KB |
Output is correct |
| 29 |
Correct |
32 ms |
1784 KB |
Output is correct |
| 30 |
Correct |
44 ms |
1760 KB |
Output is correct |
