#include<bits/stdc++.h>
#include "communication.h"
using namespace std;
struct Ranges {
long long left, right;
Ranges(long long left, long long right) : left(left), right(right) {}
bool inside(long long x) {
return left <= x && x < right;
}
long long sizeRange() {
return right - left;
}
Ranges smaller(long long start, long long s) {
return Ranges(min(right, left + start), min(right, left + start + s));
}
};
vector<Ranges> splitIntervals(vector<Ranges> v, long long start, long long s) {
vector<Ranges> right;
for(int i = 0; i < v.size(); i++){
if (s > 0 && v[i].sizeRange() - start > 0){
right.push_back(v[i].smaller(start, s));
}
s -= max(0ll, min(s, v[i].sizeRange() - start));
start -= min(start, v[i].sizeRange());
}
return right;
}
bool contains(vector<Ranges> v, long long x) {
for(int i = 0; i < v.size(); i++){
if (v[i].inside(x)){
return true;
}
}
return false;
}
struct Node {
long long s[2] = {0, 0};
vector<vector<Ranges> > v;
Node(long long N): v(2) {
s[1] = N;
v[1].emplace_back(1, N + 1);
}
Node(vector<vector<vector<Ranges> > > &cs): v(2) {
for (int g = 0; g < 2; g++)
for (vector<Ranges> &v : cs[g])
add(g, v);
}
void add(int g, Ranges it) {
s[g] += it.sizeRange();
v[g].push_back(it);
}
void add(int g, vector<Ranges> &v) {
for(int i = 0; i < v.size(); i++){
add(g, v[i]);
}
}
vector<vector<vector<Ranges> > > split() {
vector<vector<vector<Ranges> > > right(2);
for (int g = 0; g < 2; g++) {
int s1 = (s[g] + g) / 2, s2 = s[g] - s1;
right[g].push_back(splitIntervals(v[g], 0, s1));
right[g].push_back(splitIntervals(v[g], s1, s2));
}
return right;
}
long long size() {
return s[0] + s[1];
}
vector<long long> remaining() {
vector<long long> right;
for (int g = 0; g < 2; g++){
for(int i = 0; i < v[g].size(); i++){
for (long long v2 = v[g][i].left; v2 < v[g][i].right; v2++){
right.push_back(v2);
}
}
}
return right;
}
};
std::pair<int, int> solve(int N, int X = -1) {
Node s(N);
while (s.size() > 3) {
vector<vector<vector<Ranges> > > v = s.split();
int b = X != -1 ? send(contains(v[0][0], X) || contains(v[1][0], X)) : receive();
v[0].erase(v[0].begin() + b);
swap(v[0][0], v[1][b]);
s = Node(v);
}
vector<long long> right = s.remaining();
if ((int) right.size() == 3) {
int b1 = 1, b2;
for (int i = 0; i < 2 && b1; i++)
b1 = X != -1 ? send(right[0] == X || right[1] == X) : receive();
if (!b1)
b2 = X != -1 ? send(right[0] == X) : receive();
right.erase(right.begin() + (b1 ? 2 : (b2 ? 1 : 0)));
}
return make_pair(right[0], right.back());
}
void encode(int N, int X) {
solve(N, X);
}
std::pair<int, int> decode(int N) {
return solve(N);
}
Compilation message
communication.cpp: In function 'std::vector<Ranges> splitIntervals(std::vector<Ranges>, long long int, long long int)':
communication.cpp:19:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Ranges>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
19 | for(int i = 0; i < v.size(); i++){
| ~~^~~~~~~~~~
communication.cpp: In function 'bool contains(std::vector<Ranges>, long long int)':
communication.cpp:30:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Ranges>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for(int i = 0; i < v.size(); i++){
| ~~^~~~~~~~~~
communication.cpp: In member function 'void Node::add(int, std::vector<Ranges>&)':
communication.cpp:55:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Ranges>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | for(int i = 0; i < v.size(); i++){
| ~~^~~~~~~~~~
communication.cpp: In member function 'std::vector<long long int> Node::remaining()':
communication.cpp:74:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Ranges>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for(int i = 0; i < v[g].size(); i++){
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
1736 KB |
Output is correct |
| 2 |
Correct |
13 ms |
1720 KB |
Output is correct |
| 3 |
Correct |
12 ms |
1664 KB |
Output is correct |
| 4 |
Correct |
10 ms |
1684 KB |
Output is correct |
| 5 |
Correct |
14 ms |
1896 KB |
Output is correct |
| 6 |
Correct |
24 ms |
1928 KB |
Output is correct |
| 7 |
Correct |
31 ms |
1720 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
850 ms |
1724 KB |
Output is correct |
| 2 |
Correct |
390 ms |
1920 KB |
Output is correct |
| 3 |
Correct |
503 ms |
1804 KB |
Output is correct |
| 4 |
Correct |
719 ms |
1672 KB |
Output is correct |
| 5 |
Correct |
781 ms |
1708 KB |
Output is correct |
| 6 |
Correct |
500 ms |
1808 KB |
Output is correct |
| 7 |
Correct |
2196 ms |
2068 KB |
Output is correct |
| 8 |
Correct |
3456 ms |
2080 KB |
Output is correct |
| 9 |
Correct |
2994 ms |
2084 KB |
Output is correct |
| 10 |
Correct |
2963 ms |
1988 KB |
Output is correct |
| 11 |
Correct |
3094 ms |
2140 KB |
Output is correct |
| 12 |
Correct |
3098 ms |
1932 KB |
Output is correct |
| 13 |
Correct |
2934 ms |
2028 KB |
Output is correct |
| 14 |
Correct |
3158 ms |
1972 KB |
Output is correct |
| 15 |
Correct |
1593 ms |
1944 KB |
Output is correct |
| 16 |
Correct |
3652 ms |
1916 KB |
Output is correct |
| 17 |
Correct |
891 ms |
1976 KB |
Output is correct |
| 18 |
Correct |
976 ms |
1828 KB |
Output is correct |
| 19 |
Correct |
862 ms |
1916 KB |
Output is correct |
| 20 |
Correct |
912 ms |
1832 KB |
Output is correct |
| 21 |
Correct |
867 ms |
1852 KB |
Output is correct |
| 22 |
Correct |
886 ms |
1840 KB |
Output is correct |
| 23 |
Correct |
1223 ms |
1808 KB |
Output is correct |
| 24 |
Correct |
11 ms |
1660 KB |
Output is correct |
| 25 |
Correct |
10 ms |
1632 KB |
Output is correct |
| 26 |
Correct |
14 ms |
1752 KB |
Output is correct |
| 27 |
Correct |
11 ms |
1692 KB |
Output is correct |
| 28 |
Correct |
14 ms |
1656 KB |
Output is correct |
| 29 |
Correct |
25 ms |
1676 KB |
Output is correct |
| 30 |
Correct |
39 ms |
1716 KB |
Output is correct |
