//Challenge: Accepted
#include"communication.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...); }
template<class T> void pary(T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
int st = 1;
int se[16];
int str[4] = {0, 6, 9, 15};
int xo[8] = {0, 1, 2, 4, 5, 8, 9, 10};
void init() {
for (int i = 0;i < 4;i++) {
for (int j = 0;j < 8;j++) {
se[str[i] ^ xo[j]] |= 1<<i;
}
}
}
int getlen(vector<pii> t) {
int ret = 0;
for (auto p:t) ret += p.ss - p.ff + 1;
return ret;
}
vector<vector<pii> > split(vector<pii> &t) {
int len = (getlen(t) + 1) / 2;
int cur = 0;
vector<vector<pii> > ret;
vector<pii> v;
for (int i = 0;i < t.size();i++) {
pii p = t[i];
//debug("split", p.ff, p.ss);
int l = p.ss - p.ff + 1;
if (cur + l <= len) {
v.push_back(p);
cur += l;
if (cur == len) {
ret.push_back(v);
cur = 0;
v.clear();
}
} else {
v.push_back({p.ff, p.ff + len - cur - 1});
t[i].ff += len - cur;
i--;
cur = 0;
ret.push_back(v);
v.clear();
}
}
if (v.size()) {
ret.push_back(v);
v.clear();
}
while (ret.size() < 2) ret.push_back(v);
return ret;
}
vector<pii> merge(vector<pii> &s, vector<pii> &t) {
vector<pii> ret;
int ind = 0;
for (int i = 0;i < s.size();i++) {
while (ind < t.size() && t[ind].ff < s[i].ff) ret.push_back(t[ind++]);
ret.push_back(s[i]);
}
while (ind < t.size()) ret.push_back(t[ind++]);
return ret;
}
bool in(int x, vector<pii> &s) {
for (auto p:s) {
if (p.ff <= x && x <= p.ss) return 1;
}
return 0;
}
void encode(int N, int X) {
if (st) {
st = 0;
init();
}
vector<pii> A, B;
A.push_back({1, N});
while (getlen(A) + getlen(B) > 3) {
vector<vector<pii> > sa = split(A), sb = split(B);
int ask = 0;
if (in(X, sb[1])) ask = 1;
int res = send(ask);
if (res == 0) {
A = merge(sa[0], sb[0]);
B = sa[1];
} else {
A = merge(sa[1], sb[1]);
B = sa[0];
}
}
vector<pii> t = merge(A, B);
if (getlen(t) == 3) {
int enc = 1;
if (X == t[0].ff) enc = 0;
else if (X == t.back().ss) enc = 2;
for (int i = 0;i < 4;i++) send((str[enc] >>i)&1);
}
}
std::pair<int, int> decode(int N) {
if (st) {
st = 0;
init();
}
vector<pii> A, B;
A.push_back({1, N});
while (getlen(A) + getlen(B) > 3) {
vector<vector<pii> > sa = split(A), sb = split(B);
int res = receive();
if (res == 0) {
A = merge(sa[0], sb[0]);
B = sa[1];
} else {
A = merge(sa[1], sb[1]);
B = sa[0];
}
}
vector<pii> t = merge(A, B);
if (getlen(t) == 3) {
vector<int> num, ans;
for (auto p:t) {
for (int j = p.ff;j <= p.ss;j++) num.push_back(j);
}
int s = 0;
for (int i = 0;i < 4;i++) s += (1<<i) * receive();
for (int i = 0;i < 3;i++) {
if ((se[s]>>i)&1) ans.push_back(num[i]);
}
return {ans[0], ans.back()};
} else {
return {t[0].ff, t.back().ss};
}
}
Compilation message
communication.cpp: In function 'std::vector<std::vector<std::pair<int, int> > > split(std::vector<std::pair<int, int> >&)':
communication.cpp:44:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for (int i = 0;i < t.size();i++) {
| ~~^~~~~~~~~~
communication.cpp: In function 'std::vector<std::pair<int, int> > merge(std::vector<std::pair<int, int> >&, std::vector<std::pair<int, int> >&)':
communication.cpp:75:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for (int i = 0;i < s.size();i++) {
| ~~^~~~~~~~~~
communication.cpp:76:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | while (ind < t.size() && t[ind].ff < s[i].ff) ret.push_back(t[ind++]);
| ~~~~^~~~~~~~~~
communication.cpp:79:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | while (ind < t.size()) ret.push_back(t[ind++]);
| ~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
1700 KB |
Output is correct |
| 2 |
Correct |
9 ms |
1700 KB |
Output is correct |
| 3 |
Correct |
15 ms |
1656 KB |
Output is correct |
| 4 |
Correct |
10 ms |
1716 KB |
Output is correct |
| 5 |
Correct |
13 ms |
1620 KB |
Output is correct |
| 6 |
Correct |
34 ms |
1896 KB |
Output is correct |
| 7 |
Correct |
53 ms |
1600 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
433 ms |
200 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
