#include "Anna.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
//common
#define send_f SendA
const int anna_bits = 18, len_bits = 4;
int get_bit(int msk, int i) {
return (msk >> i) & 1;
}
int equal_bits, step;
struct BitIO {
int read_val = 0;
queue<int> val_buffer, reads;
bool process_read(bool bit) {
if(reads.size()) {
read_val = 2 * read_val + bit;
reads.front()--;
if(reads.front() == 0) {
val_buffer.push(read_val);
reads.pop();
read_val = 0;
}
}
return reads.size();
}
void order_read(int x) {
if(x) {
reads.push(x);
}
}
int extract_read() {
int ret = val_buffer.front();
val_buffer.pop();
return ret;
}
void send_bits(int msk, int x) {
for(int i = x; i--;)
send_f(get_bit(msk, i));
}
};
BitIO io;
//end common
int n, l, r;
int l1, l2, r1, r2;
vector<int> p;
} // namespace
void InitA(int n_, int l_, int r_) {
n = n_, l = l_, r = r_;
p.resize(1<<20, 1<<20);
for(int i = 19; i >= 0 &&
get_bit(l, i) == get_bit(r, i); i--)
equal_bits++;
equal_bits = min(equal_bits, anna_bits - len_bits);
int pos = r_ >> (20 - equal_bits);
io.send_bits(equal_bits, len_bits);
io.send_bits(pos, equal_bits);
io.order_read(20);
io.order_read(20);
step = 4 + equal_bits;
int B = (1 << (19 - equal_bits));
pos = (pos << (20 - equal_bits)) + B;
l1 = r1 = pos;//get_segment(1)
l2 = pos - B;//get_segment(2*B)
r2 = pos + B;
}
void ReceiveA(bool x) {
if(io.process_read(x))
return;
if(step < anna_bits) {
int ll = io.extract_read(), rr = io.extract_read();
cerr << "Alice " << step << " " << l << " " << r << endl;
cerr << "ll, rr: " << ll << " " << rr << endl;
int contains = l <= ll && rr <= rr;
SendA(contains);
if(contains) {
l1 = ll, r1 = rr;
} else {
l2 = ll, r2 = rr;
}
step++;
}
if(step < anna_bits) {
io.order_read(20);
io.order_read(20);
} else if(step == anna_bits) {
io.order_read(20);
io.order_read(20);
io.order_read(20);
io.order_read(20);
step++;
} else {
l1 = io.extract_read();
r1 = io.extract_read();
l2 = io.extract_read();
r2 = io.extract_read();
for(int i = l2; i <= l1; i++)
io.order_read(20);
io.order_read(20);
io.order_read(20);
for(int i = r1; i <= r2; i++)
io.order_read(20);
}
}
int Answer() {
for(int i = l2; i <= l1; i++) {
p[i] = io.extract_read();
}
int mn_pos = io.extract_read();
p[mn_pos] = io.extract_read();
for(int i = r1; i <= r2; i++) {
p[i] = io.extract_read();
}
int pos = min_element(p.begin(), p.end()) - p.begin();
cerr << "final: " << pos << " : " << l1 << " " << r1 << " " << l2 << " " << r2 << endl;
return pos;
}
#include "Bruno.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
//common
#define send_f SendB
const int anna_bits = 18, len_bits = 4;
int get_bit(int msk, int i) {
return (msk >> i) & 1;
}
int equal_bits, step;
struct BitIO {
int read_val = 0;
queue<int> val_buffer, reads;
bool process_read(bool bit) {
if(reads.size()) {
read_val = 2 * read_val + bit;
reads.front()--;
if(reads.front() == 0) {
val_buffer.push(read_val);
reads.pop();
read_val = 0;
}
}
return reads.size();
}
void order_read(int x) {
if(x) {
reads.push(x);
}
}
int extract_read() {
int ret = val_buffer.front();
val_buffer.pop();
return ret;
}
void send_bits(int msk, int x) {
for(int i = x; i--;)
send_f(get_bit(msk, i));
}
};
BitIO io;
//end common
int n, pos, L, R, low, high;
vector<int> p;
} // namespace
void InitB(int N, std::vector<int> P) {
n = N;
n = max(n, 1<<20);
p = P;
while(p.size() < n)
p.push_back(1 + p.size());
step = -1;
io.order_read(len_bits);
}
array<int, 2> get_segment(int len) {
int l = pos, r = pos, cur_min = p[pos];
for(len -= 1; len; len--) {
if(l > L && p[l - 1] > cur_min) {
l--;
} else if(r + 1 < R && p[r + 1] > cur_min) {
r++;
} else if(l > L && (r + 1 == R || p[l - 1] > p[r + 1])) {
cur_min = p[--l];
} else {
cur_min = p[++r];
}
cout << l << " " << r << endl;
}
return {l, r};
}
void ReceiveB(bool y) {
if(io.process_read(y))
return;
if(step == -1) {
equal_bits = io.extract_read();
low = 1;
high = 1<<(20 - equal_bits);
if(equal_bits) {
io.order_read(equal_bits);
step = -2;
return;
} else {
pos = 1<<19;
L = 0;
R = 1<<20;
step = 0;
}
}
if(step == -2) {
pos = (io.extract_read()<<(20 - equal_bits));
int B = 1<<(19 - equal_bits);
pos += B;
L = pos - B;
R = pos + B;
step = equal_bits;
}
cerr << "Bruno: " << step << " " << pos << " " << equal_bits << endl;
cerr << "L, R: " << " " << L << " " << R << endl;
cerr << "low, high: " << " " << low << " " << high << endl;
if(step == anna_bits - len_bits) {//final iteration
auto [l1, r1] = get_segment(low);
auto [l2, r2] = get_segment(high);
io.send_bits(l1, 20);
io.send_bits(r1, 20);
io.send_bits(l2, 20);
io.send_bits(r2, 20);
cerr << "final: " << pos << " : " << l1 << " " << r1 << " " << l2 << " " << r2 << endl;
for(int i = l2; i <= l1; i++) {
io.send_bits(p[i], 20);
}
int mn_pos = min_element(p.begin() + l1, p.begin() + r1 + 1) - p.begin();
io.send_bits(mn_pos, 20);
io.send_bits(p[mn_pos], 20);
for(int i = r1; i <= r2; i++) {
io.send_bits(p[i], 20);
}
return;
}
int mid = (low + high) / 2;
if(step > equal_bits) {
if(y)
low = mid;
else
high = mid;
mid = (low + high) / 2;
cerr << "update low, high: " << low << " " << high << endl;
}
auto [l, r] = get_segment(mid);
cerr << "send (l, r) = (" << l << ", " << r << ") | mid = " << mid << endl;
io.send_bits(l, 20);
io.send_bits(r, 20);
step++;
}
Compilation message
Anna.cpp: In function 'void ReceiveA(bool)':
Anna.cpp:84:38: warning: self-comparison always evaluates to true [-Wtautological-compare]
84 | int contains = l <= ll && rr <= rr;
| ~~ ^~ ~~
Bruno.cpp: In function 'void InitB(int, std::vector<int>)':
Bruno.cpp:56:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
56 | while(p.size() < n)
| ~~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
4296 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
4296 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
4372 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
