#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);
for (pii p : ins) s.insert(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();
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;
}
}
}
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);
for (pii p : ins) s.insert(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();
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 |
Correct |
5 ms |
2764 KB |
Output is correct |
| 2 |
Correct |
12 ms |
2976 KB |
Output is correct |
| 3 |
Correct |
7 ms |
2760 KB |
Output is correct |
| 4 |
Correct |
7 ms |
2936 KB |
Output is correct |
| 5 |
Correct |
8 ms |
2924 KB |
Output is correct |
| 6 |
Correct |
15 ms |
2696 KB |
Output is correct |
| 7 |
Correct |
18 ms |
2940 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
460 ms |
2756 KB |
Output is partially correct |
| 2 |
Partially correct |
258 ms |
2764 KB |
Output is partially correct |
| 3 |
Partially correct |
355 ms |
2760 KB |
Output is partially correct |
| 4 |
Partially correct |
570 ms |
2740 KB |
Output is partially correct |
| 5 |
Partially correct |
427 ms |
2724 KB |
Output is partially correct |
| 6 |
Partially correct |
360 ms |
2744 KB |
Output is partially correct |
| 7 |
Partially correct |
1638 ms |
3104 KB |
Output is partially correct |
| 8 |
Partially correct |
2577 ms |
3004 KB |
Output is partially correct |
| 9 |
Partially correct |
2163 ms |
2936 KB |
Output is partially correct |
| 10 |
Partially correct |
2415 ms |
3208 KB |
Output is partially correct |
| 11 |
Partially correct |
2276 ms |
3124 KB |
Output is partially correct |
| 12 |
Partially correct |
2284 ms |
2928 KB |
Output is partially correct |
| 13 |
Partially correct |
2001 ms |
3072 KB |
Output is partially correct |
| 14 |
Partially correct |
2052 ms |
2844 KB |
Output is partially correct |
| 15 |
Partially correct |
1108 ms |
2888 KB |
Output is partially correct |
| 16 |
Partially correct |
2184 ms |
2876 KB |
Output is partially correct |
| 17 |
Partially correct |
570 ms |
2828 KB |
Output is partially correct |
| 18 |
Partially correct |
554 ms |
2792 KB |
Output is partially correct |
| 19 |
Partially correct |
585 ms |
2784 KB |
Output is partially correct |
| 20 |
Partially correct |
571 ms |
2800 KB |
Output is partially correct |
| 21 |
Partially correct |
543 ms |
2784 KB |
Output is partially correct |
| 22 |
Partially correct |
603 ms |
2884 KB |
Output is partially correct |
| 23 |
Partially correct |
907 ms |
3324 KB |
Output is partially correct |
| 24 |
Correct |
2 ms |
3128 KB |
Output is correct |
| 25 |
Correct |
5 ms |
2748 KB |
Output is correct |
| 26 |
Correct |
4 ms |
2776 KB |
Output is correct |
| 27 |
Correct |
4 ms |
2940 KB |
Output is correct |
| 28 |
Correct |
4 ms |
2744 KB |
Output is correct |
| 29 |
Correct |
9 ms |
2852 KB |
Output is correct |
| 30 |
Correct |
15 ms |
2764 KB |
Output is correct |
