This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//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 maxn 200005
#define maxc 31
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
int se[16];
int str[4] = {0, 6, 9, 15};
int xo[7] = {1, 2, 4, 5, 8, 9, 10};
void init() {
for (int i = 0;i < 4;i++) {
for (int j = 0;j < 7;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) + 3) / 4;
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});
cur = 0;
ret.push_back(v);
v.clear();
t[i].ff += len - cur;
i--;
}
}
if (v.size()) {
ret.push_back(v);
v.clear();
}
while (ret.size() < 4) ret.push_back(v);
return ret;
}
int st = 1;
void encode(int N, int X) {
if (st) {
st = 0;
init();
}
vector<pii> t;
t.push_back({1, N});
while (getlen(t) > 2) {
debug("t");
for (auto p:t) debug(p.ff, p.ss);
debug();
vector<vector<pii> > s = split(t);
int p = 0, r = 0, id = 0;
for (int i = 0;i < 4;i++) {
for (auto j:s[i]) debug(j.ff, j.ss);
debug();
int mi = s[i][0].ff, ma = s[i].back().ss;
if (mi <= X && X <= ma) {
id = i;
p = str[i];
break;
}
}
debug(id);
for (int i = 0;i < 4;i++) {
r += (1<<i) * send((p >> i) & 1);
}
r = se[r];
vector<pii> to = s[id];
for (int i = 0;i < 4;i++) {
if (i != id && ((r >> i) & 1)) {
to.insert(to.end(), s[i].begin(), s[i].end());
}
}
t = to;
}
}
std::pair<int, int> decode(int N) {
if (st) {
st = 0;
init();
}
vector<pii> t;
t.push_back({1, N});
while (getlen(t) > 2) {
debug("t");
for (auto p:t) debug(p.ff, p.ss);
debug();
vector<vector<pii> > s = split(t);
int r = 0;
for (int i = 0;i < 4;i++) {
r += (1<<i) * receive();
}
debug(r);
r = se[r];
vector<pii> to;
for (int i = 0;i < 4;i++) {
if (((r >> i) & 1)) {
debug(i);
to.insert(to.end(), s[i].begin(), s[i].end());
}
}
t = to;
}
return {t[0].ff, t.back().ss};
}
Compilation message (stderr)
communication.cpp: In function 'std::vector<std::vector<std::pair<int, int> > > split(std::vector<std::pair<int, int> >)':
communication.cpp:45: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]
45 | for (int i = 0;i < t.size();i++) {
| ~~^~~~~~~~~~
communication.cpp: In function 'void encode(int, int)':
communication.cpp:13:20: warning: statement has no effect [-Wunused-value]
13 | #define debug(...) 0
| ^
communication.cpp:84:3: note: in expansion of macro 'debug'
84 | debug("t");
| ^~~~~
communication.cpp:13:20: warning: statement has no effect [-Wunused-value]
13 | #define debug(...) 0
| ^
communication.cpp:85:18: note: in expansion of macro 'debug'
85 | for (auto p:t) debug(p.ff, p.ss);
| ^~~~~
communication.cpp:85:13: warning: variable 'p' set but not used [-Wunused-but-set-variable]
85 | for (auto p:t) debug(p.ff, p.ss);
| ^
communication.cpp:13:20: warning: statement has no effect [-Wunused-value]
13 | #define debug(...) 0
| ^
communication.cpp:86:3: note: in expansion of macro 'debug'
86 | debug();
| ^~~~~
communication.cpp:13:20: warning: statement has no effect [-Wunused-value]
13 | #define debug(...) 0
| ^
communication.cpp:90:22: note: in expansion of macro 'debug'
90 | for (auto j:s[i]) debug(j.ff, j.ss);
| ^~~~~
communication.cpp:90:14: warning: variable 'j' set but not used [-Wunused-but-set-variable]
90 | for (auto j:s[i]) debug(j.ff, j.ss);
| ^
communication.cpp:13:20: warning: statement has no effect [-Wunused-value]
13 | #define debug(...) 0
| ^
communication.cpp:91:4: note: in expansion of macro 'debug'
91 | debug();
| ^~~~~
communication.cpp:13:20: warning: statement has no effect [-Wunused-value]
13 | #define debug(...) 0
| ^
communication.cpp:99:3: note: in expansion of macro 'debug'
99 | debug(id);
| ^~~~~
communication.cpp: In function 'std::pair<int, int> decode(int)':
communication.cpp:13:20: warning: statement has no effect [-Wunused-value]
13 | #define debug(...) 0
| ^
communication.cpp:123:3: note: in expansion of macro 'debug'
123 | debug("t");
| ^~~~~
communication.cpp:13:20: warning: statement has no effect [-Wunused-value]
13 | #define debug(...) 0
| ^
communication.cpp:124:18: note: in expansion of macro 'debug'
124 | for (auto p:t) debug(p.ff, p.ss);
| ^~~~~
communication.cpp:124:13: warning: variable 'p' set but not used [-Wunused-but-set-variable]
124 | for (auto p:t) debug(p.ff, p.ss);
| ^
communication.cpp:13:20: warning: statement has no effect [-Wunused-value]
13 | #define debug(...) 0
| ^
communication.cpp:125:3: note: in expansion of macro 'debug'
125 | debug();
| ^~~~~
communication.cpp:13:20: warning: statement has no effect [-Wunused-value]
13 | #define debug(...) 0
| ^
communication.cpp:132:3: note: in expansion of macro 'debug'
132 | debug(r);
| ^~~~~
communication.cpp:13:20: warning: statement has no effect [-Wunused-value]
13 | #define debug(...) 0
| ^
communication.cpp:137:5: note: in expansion of macro 'debug'
137 | debug(i);
| ^~~~~| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
