#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 end){
return Ranges(min(right, left + start), min(right, left + start + end));
}
};
vector<Ranges> splitIntervals(vector<Ranges> v, long long start, long long end) {
vector<Ranges> r;
for (Ranges &it : v) {
if (end > 0 && it.sizeRange() - start > 0){
r.push_back(it.Smaller(start, end));
}
end -= max(0LL, min(end, it.sizeRange() - start));
start -= min(start, it.sizeRange());
}
return r;
}
bool contains(vector<Ranges> v, long long x) {
for (Ranges &it : v){
if (it.inside(x)){
return true;
}
}
return false;
}
struct Node {
long long end[2] = {0, 0};
vector<vector<Ranges> > v;
Node(long long N): v(2) {
end[1] = N;
v[1].emplace_back(1, N + 1);
}
Node(vector<vector<vector<Ranges> > > &v2): v(2) {
for (long long g = 0; g < 2; g++){
for (vector<Ranges> &v : v2[g]){
add(g, v);
}
}
}
void add(long long g, Ranges it) {
end[g] += it.sizeRange();
v[g].push_back(it);
}
void add(long long x, vector<Ranges> &v) {
for (Ranges &it : v){
add(x, it);
}
}
vector<vector<vector<Ranges> > > split() {
vector<vector<vector<Ranges> > > r(2);
for (long long g = 0; g < 2; g++) {
long long s1 = (end[g] + g) / 2, s2 = end[g] - s1;
r[g].push_back(splitIntervals(v[g], 0, s1));
r[g].push_back(splitIntervals(v[g], s1, s2));
}
return r;
}
long long size() {
return end[0] + end[1];
}
vector<long long> remaining() {
vector<long long> r;
for (long long g = 0; g < 2; g++){
for (Ranges &it : v[g]){
for (long long v = it.left; v < it.right; v++){
r.push_back(v);
}
}
}
return r;
}
};
pair<long long, long long> solve(long long N, long long X) {
Node v2(N);
while (v2.size() > 3) {
vector<vector<vector<Ranges> > > v = v2.split();
long long 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]);
v2 = Node(v);
}
vector<long long> r = v2.remaining();
if ((long long) r.size() == 3) {
long long b1 = 1, b2;
for (long long i = 0; i < 2 && b1; i++){
b1 = X != -1 ? send(r[0] == X || r[1] == X) : receive();
if (!b1){
b2 = X != -1 ? send(r[0] == X) : receive();
r.erase(r.begin() + (b1 ? 2 : (b2 ? 1 : 0)));
}
}
}
return {r[0], r.back()};
}
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 |
Incorrect |
3 ms |
280 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
359 ms |
292 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
