#include <bits/stdc++.h>
#define MODE 0
using namespace std;
using ll = long long;
using pii = pair<int, int>;
int send(int s)
#if MODE
{
cout << "send " << s << endl;
cin >> s;
return s;
}
#else
;
#endif
int receive()
#if MODE
{
cout << "receive: " << flush;
int s;
cin >> s;
return s;
}
#else
;
#endif
int write(int s) {
//cout << "w: " << s << '\n';
if (s == 1) {
int p = 0;
while (p == 0) p = send(1);
return send(1) + 2;
} else {
int p = 2;
while (p--) if (send(0)) return send(3 - s) + 2;
return 1;
}
}
const int N = 1e9;
void encode(int n, int x) {
set<pii> s;
s.insert({1, N + 1});
int len = N;
while (len > 2) {
int mid1 = len / 3;
int mid2 = 2 * len / 3;
int cum = 0;
for (pii p : s) {
if (x >= p.second) cum += p.second - p.first;
else {
cum += x - p.first;
break;
}
}
int b;
if (cum < mid1) b = write(1);
else if (cum < mid2) b = write(2);
else b = write(3);
//cout << "r: " << b << '\n';
set<pii> l, r, era, ins;
int cur = 0;
for (pii p : s) {
if (cur == mid1) break;
if (cur + p.second - p.first <= mid1) {
l.insert(p);
era.insert(p);
cur += p.second - p.first;
} else {
l.insert({p.first, p.first + mid1 - cur});
ins.insert({p.first + mid1 - cur, p.second});
era.insert(p);
cur = mid1;
}
}
for (pii p : era) s.erase(p);
era.clear();
ins.clear();
for (pii p : s) {
if (cur == mid2) break;
if (cur + p.second - p.first <= mid2) {
r.insert(p);
era.insert(p);
cur += p.second - p.first;
} else {
r.insert({p.first, p.first + mid2 - cur});
ins.insert({p.first + mid2 - cur, p.second});
era.insert(p);
cur = mid2;
}
}
for (pii p : era) s.erase(p);
for (pii p : ins) s.insert(p);
era.clear();
if (b == 1) {
for (pii p : r) s.insert(p);
len -= mid1;
} else if (b == 2) {
for (pii p : l) s.insert(p);
len -= mid2 - mid1;
} else {
for (pii p : r) l.insert(p);
swap(l, s);
len -= len - mid2;
}
}
}
int read() {
if (receive()) return receive() + 2;
if (receive()) return receive() + 2;
return 1;
}
pair<int, int> decode(int n) {
set<pii> s;
s.insert({1, N + 1});
int len = N;
while (len > 2) {
int mid1 = len / 3;
int mid2 = 2 * len / 3;
int b = read();
set<pii> l, r, era, ins;
int cur = 0;
for (pii p : s) {
if (cur == mid1) break;
if (cur + p.second - p.first <= mid1) {
l.insert(p);
era.insert(p);
cur += p.second - p.first;
} else {
l.insert({p.first, p.first + mid1 - cur});
ins.insert({p.first + mid1 - cur, p.second});
era.insert(p);
cur = mid1;
}
}
for (pii p : era) s.erase(p);
era.clear();
for (pii p : s) {
if (cur == mid2) break;
if (cur + p.second - p.first <= mid2) {
r.insert(p);
era.insert(p);
cur += p.second - p.first;
} else {
r.insert({p.first, p.first + mid2 - cur});
ins.insert({p.first + mid2 - cur, p.second});
era.insert(p);
cur = mid2;
}
}
for (pii p : era) s.erase(p);
for (pii p : ins) s.insert(p);
era.clear();
ins.clear();
if (b == 1) {
for (pii p : r) s.insert(p);
len -= mid1;
} else if (b == 2) {
for (pii p : l) s.insert(p);
len -= mid2 - mid1;
} else {
for (pii p : r) l.insert(p);
swap(l, s);
len -= len - mid2;
}
}
if (s.size() == 1) return {s.begin()->first, s.begin()->first+1};
else {
pii p;
auto it = s.begin();
p.first = it->first;
++it;
p.second = it->first;
return p;
}
}
#if MODE
int main() {
cin.tie(0) -> sync_with_stdio(0);
int n, x;
cin >> n >> x;
encode(n, x);
cout << "\n\nmode swich\n\n\n";
pair<int, int> p = decode(n);
cout << "! " << p.first << ' ' << p.second << endl;
}
#endif
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
512 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
271 ms |
332 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
