#include "encoder.h"
#include "encoderlib.h"
#include "decoder.h"
#include "decoderlib.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define vt vector
#define pb push_back
#define X first
#define Y second
using pii = pair<int,int>;
#define debug(x) do\
{auto _x=x; cerr<<#x<<" = "<<_x<<'\n';}while(0);
#define f0r(i,a,b) for(auto i=(a);i<(b);i++)
#define r0f(i,a,b) for(auto i=(a);i>=(b);i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
//Stars and bars
//320 elements, 255 splitting points
//C(575, 255)
//from [0, 256)
//Convert bits into big integer
//be careful of leading 0s in decoder
//Find R-th combination: C(n,k,R)
//then sweep thru, unchosen elements = d
//chosen elements -> d++
//bug: chosen elements don't count towards total
//account for leading 0s
//use binary search lemma
//encoding: message -> (str append) bits -> (roll) order number
//-> (swipe + myror) chosen -> (splay) sorted sequence
// 100 * 9 bits
namespace {
const long long base = 1e9;
using ll = vt<int>;
const int digits = 123;
ll itov(int k) {
vt<int> res (digits);
res[digits-1] = k;
return res;
}
vt<vt<ll>> cdp (600, vt<ll> (600, itov(-1)));
ostream& operator<<(ostream &lol, const ll &a) {
bool IS_BIGNUM = sz(a) == digits;
int lz = 0;
if(IS_BIGNUM) {
while(lz < sz(a) and a[lz] == 0) lz++; //BUG: almost segfaulted
}
//BUG: size of a instead of digits
f0r(i,lz,sz(a)) {
if(i == lz) lol << a[i] << ' ';
else lol << a[i] << ' ';
}
if(lz >= sz(a) and lz != 0) lol << 0;
return lol;
}
ll operator+(const ll &a, const ll &b) {
ll c (digits);
int carry = 0;
r0f(i,digits-1,0) {
long long sum = (a[i] + b[i] + carry);
c[i] = sum % base;
carry = sum / base;
}
// debug(a) debug(b) debug(c)
return c;
}
ll operator-(const ll &a, const ll &b) {
assert(a >= b);
ll c (digits);
int carry = 0;
r0f(i,digits-1,0) {
long long diff = (a[i] - b[i] - carry);
int nc = 0;
while(diff < 0) nc++, diff += base;
c[i] = diff;
//BUG: forgot to set c[i] = diff
carry = nc;
}
// debug(a)
// debug(b)
// debug(c);
return c;
}
ll operator/(const ll &a, int b) { //short division
ll res (digits);
int carry = 0;
f0r(i,0,digits) {
int ds = carry * base + a[i];
res[i] = ds / b;
carry = ds % b;
}
// debug(a) debug(res)
return res;
}
ll comb(int n, int k) {
if(k == 0) return itov(1);
if(n == 0) return itov(0);
if(cdp[n][k] != itov(-1)) return cdp[n][k];
return cdp[n][k] = comb(n-1,k-1) + comb(n-1,k);
}
//BUG: RE = Infinite recursion
//Also, don't use directly
void swipe(int n, int k, ll R, vt<int> &ans) {
if(n == 0 or k == 0) return;
// debug(n) debug(k) debug(R)
ll a = comb(n-1,k);
ll b = comb(n-1,k-1);
// debug(a) debug(b)
// assert(R <= (a+b)); currently buggy??
// if(R <= a) {
// swipe(n-1,k,R,ans);
// } else {
// swipe(n-1,k-1,R-a,ans);
// ans.pb(n-1); //0-indexing business
// }
assert(R <= (a+b));
// debug(R)
if(R <= b) {
// debug("I chose") debug(n) debug(k)
ans.pb(n-1);
swipe(n-1,k-1,R,ans);
} else {
// debug("I didn't choose") debug(n) debug(k)
swipe(n-1,k,R-b,ans);
}
}
//This function should work
vt<int> myror(int n, int k, ll R) {
vt<int> ans;
swipe(n, k, R, ans);
f0r(i,0,sz(ans)) {
ans[i] = n-1-ans[i];
}
// debug(n) debug(k) debug(R)
// debug(ans);
return ans;
}
vt<int> splay(vt<int> co, int N) {
debug("splay")
const int sbars = 5*N + 255;
vt<bool> chose (sbars);
f0r(i,0,sz(co)) {
assert(co[i] < sbars);
chose[co[i]] = 1;
}
vt<int> res;
int d = 0;
f0r(i,0,sbars) {
if(chose[i]) {
d++;
} else {
res.pb(d);
}
}
return res;
}
//decoding: sorted sequence -> (while loop and cur diff) chosen -> (guess binary search, div2) order number
//->(division roll method) bits -> (pad zeroes and stoi spam) message
void mydec(signed msz, signed N, signed xs[]) {
sort(xs,xs+N);
int ck = 255;
int cn = N + 255;
debug(cn) debug(ck);
vt<int> chose; //0,1 array
int c_walk = 0;
f0r(i,0,N) {
while(c_walk != xs[i]) c_walk++, chose.pb(1);
chose.pb(0);
}
//BUG: mixed up order of operations LMAO
//need to account for leading zeroes before constructing need, otherwise useless
//edge case: ending 1s
while(c_walk != 255) c_walk++, chose.pb(1);
vt<int> need; //chosen elements
f0r(i,0,sz(chose)) {
if(chose[i]) {
need.pb(i);
}
}
ll lo = itov(1), hi = itov(1), ord = itov(-1);
f0r(_,0,8*65) { //repeated doublings???
hi = hi + hi;
}
//binary search on order number
auto check = [&](ll wow) -> bool {
//BUG: check if wow is even in the order number range
if(wow > comb(cn, ck)) {
return false;
}
vt<int> cur = myror(cn, ck, wow);
if(cur <= need) {
return true;
} else {
return false;
}
};
debug(need);
while(lo <= hi) {
ll mid = (lo+hi)/2;
// debug(lo) debug(hi) debug(mid)
// debug(mid+itov(1));
// debug(mid-itov(1));
if(check(mid)) {
lo = mid+itov(1);
ord = mid;
} else {
hi = mid-itov(1);
}
}
if(myror(cn,ck,ord+itov(6)) == need) {
debug("WTF");
}
assert(myror(cn,ck,ord) == need);
debug(ord);
//BUG: order number + 1
ll pay = ord - itov(1);
string bits;
while(pay != itov(0)) { //BUG: Inf loop here
if(pay[digits-1] % 2 == 1) {
bits += '1';
} else {
bits += '0';
}
//BUG: lmao forgot to set pay = pay/2
pay = pay / 2;
}
while(sz(bits) != 8 * msz) { //bit string
bits += '0';
}
reverse(all(bits));
assert(sz(bits) % 8 == 0);
vt<int> ans;
debug("DECODING BITS")
debug(bits);
for(int ptr = 0; ptr < sz(bits); ptr += 8) {
string block = bits.substr(ptr, 8);
int ayy = stoi(block, nullptr, 2);
ans.pb(ayy);
}
debug("I THINK...")
for(int x : ans) {
cerr << x << ' ';
output(x);
}
cerr << '\n';
}
};
void encode(signed N, signed M[]) {
// cdp = vt<vt<ll>> (600, vt<ll> (600, -1));
// assert(N == 8);
string bits;
//load input bit and trick
//BUG: highest significant bit first, lmao
f0r(i,0,N) {
r0f(b,7,0) {
if(M[i] & (1 << b)) {
bits += '1';
} else {
bits += '0';
}
}
}
debug("ENCODING BITS")
debug(bits);
ll ord = itov(0);
ll roll = itov(1);
debug("ayo")
r0f(i,sz(bits)-1,0) {
if(bits[i] == '1') {
ord = ord + roll;
}
roll = roll + roll;
}
ord = ord + itov(1); //BUG: 0 case is bad
debug(ord);
//bug: forgot to + 255
vt<int> co = myror(5*N + 255, 255, ord);
// debug(ord);
// swipe(575,255,ord,co);
// debug(co);
debug(co);
vt<int> ans = splay(co, N);
assert(sz(ans) == 5*N);
debug("here's my answer");
for(int x : ans) {
cerr << x << ' ';
}
cerr << '\n';
for(int x : ans) {
send(x);
}
}
// void decode(signed msz, signed N, signed xs[]) {
// mydec(msz, N, xs);
// }
#include "decoder.h"
#include "decoderlib.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define vt vector
#define pb push_back
#define X first
#define Y second
using pii = pair<int,int>;
#define debug(x) do\
{auto _x=x; cerr<<#x<<" = "<<_x<<'\n';}while(0);
#define f0r(i,a,b) for(auto i=(a);i<(b);i++)
#define r0f(i,a,b) for(auto i=(a);i>=(b);i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
namespace {
const long long base = 1e9;
using ll = vt<int>;
const int digits = 123;
ll itov(int k) {
vt<int> res (digits);
res[digits-1] = k;
return res;
}
vt<vt<ll>> cdp (600, vt<ll> (600, itov(-1)));
ostream& operator<<(ostream &lol, const ll &a) {
bool IS_BIGNUM = sz(a) == digits;
int lz = 0;
if(IS_BIGNUM) {
while(lz < sz(a) and a[lz] == 0) lz++; //BUG: almost segfaulted
}
//BUG: size of a instead of digits
f0r(i,lz,sz(a)) {
if(i == lz) lol << a[i] << ' ';
else lol << a[i] << ' ';
}
if(lz >= sz(a) and lz != 0) lol << 0;
return lol;
}
ll operator+(const ll &a, const ll &b) {
ll c (digits);
int carry = 0;
r0f(i,digits-1,0) {
long long sum = (a[i] + b[i] + carry);
c[i] = sum % base;
carry = sum / base;
}
// debug(a) debug(b) debug(c)
return c;
}
ll operator-(const ll &a, const ll &b) {
assert(a >= b);
ll c (digits);
int carry = 0;
r0f(i,digits-1,0) {
long long diff = (a[i] - b[i] - carry);
int nc = 0;
while(diff < 0) nc++, diff += base;
c[i] = diff;
//BUG: forgot to set c[i] = diff
carry = nc;
}
// debug(a)
// debug(b)
// debug(c);
return c;
}
ll operator/(const ll &a, int b) { //short division
ll res (digits);
int carry = 0;
f0r(i,0,digits) {
int ds = carry * base + a[i];
res[i] = ds / b;
carry = ds % b;
}
// debug(a) debug(res)
return res;
}
ll comb(int n, int k) {
if(k == 0) return itov(1);
if(n == 0) return itov(0);
if(cdp[n][k] != itov(-1)) return cdp[n][k];
return cdp[n][k] = comb(n-1,k-1) + comb(n-1,k);
}
//BUG: RE = Infinite recursion
//Also, don't use directly
void swipe(int n, int k, ll R, vt<int> &ans) {
if(n == 0 or k == 0) return;
// debug(n) debug(k) debug(R)
ll a = comb(n-1,k);
ll b = comb(n-1,k-1);
// debug(a) debug(b)
// assert(R <= (a+b)); currently buggy??
// if(R <= a) {
// swipe(n-1,k,R,ans);
// } else {
// swipe(n-1,k-1,R-a,ans);
// ans.pb(n-1); //0-indexing business
// }
assert(R <= (a+b));
// debug(R)
if(R <= b) {
// debug("I chose") debug(n) debug(k)
ans.pb(n-1);
swipe(n-1,k-1,R,ans);
} else {
// debug("I didn't choose") debug(n) debug(k)
swipe(n-1,k,R-b,ans);
}
}
//This function should work
vt<int> myror(int n, int k, ll R) {
vt<int> ans;
swipe(n, k, R, ans);
f0r(i,0,sz(ans)) {
ans[i] = n-1-ans[i];
}
// debug(n) debug(k) debug(R)
// debug(ans);
return ans;
}
vt<int> splay(vt<int> co, int N) {
debug("splay")
const int sbars = 5*N + 255;
vt<bool> chose (sbars);
f0r(i,0,sz(co)) {
assert(co[i] < sbars);
chose[co[i]] = 1;
}
vt<int> res;
int d = 0;
f0r(i,0,sbars) {
if(chose[i]) {
d++;
} else {
res.pb(d);
}
}
return res;
}
//decoding: sorted sequence -> (while loop and cur diff) chosen -> (guess binary search, div2) order number
//->(division roll method) bits -> (pad zeroes and stoi spam) message
void mydec(signed msz, signed N, signed xs[]) {
sort(xs,xs+N);
int ck = 255;
int cn = N + 255;
debug(cn) debug(ck);
vt<int> chose; //0,1 array
int c_walk = 0;
f0r(i,0,N) {
while(c_walk != xs[i]) c_walk++, chose.pb(1);
chose.pb(0);
}
//BUG: mixed up order of operations LMAO
//need to account for leading zeroes before constructing need, otherwise useless
//edge case: ending 1s
while(c_walk != 255) c_walk++, chose.pb(1);
vt<int> need; //chosen elements
f0r(i,0,sz(chose)) {
if(chose[i]) {
need.pb(i);
}
}
ll lo = itov(1), hi = itov(1), ord = itov(-1);
f0r(_,0,8*65) { //repeated doublings???
hi = hi + hi;
}
//binary search on order number
auto check = [&](ll wow) -> bool {
//BUG: check if wow is even in the order number range
if(wow > comb(cn, ck)) {
return false;
}
vt<int> cur = myror(cn, ck, wow);
if(cur <= need) {
return true;
} else {
return false;
}
};
debug(need);
while(lo <= hi) {
ll mid = (lo+hi)/2;
// debug(lo) debug(hi) debug(mid)
// debug(mid+itov(1));
// debug(mid-itov(1));
if(check(mid)) {
lo = mid+itov(1);
ord = mid;
} else {
hi = mid-itov(1);
}
}
if(myror(cn,ck,ord+itov(6)) == need) {
debug("WTF");
}
assert(myror(cn,ck,ord) == need);
debug(ord);
//BUG: order number + 1
ll pay = ord - itov(1);
string bits;
while(pay != itov(0)) { //BUG: Inf loop here
if(pay[digits-1] % 2 == 1) {
bits += '1';
} else {
bits += '0';
}
//BUG: lmao forgot to set pay = pay/2
pay = pay / 2;
}
while(sz(bits) != 8 * msz) { //bit string
bits += '0';
}
reverse(all(bits));
assert(sz(bits) % 8 == 0);
vt<int> ans;
debug("DECODING BITS")
debug(bits);
for(int ptr = 0; ptr < sz(bits); ptr += 8) {
string block = bits.substr(ptr, 8);
int ayy = stoi(block, nullptr, 2);
ans.pb(ayy);
}
debug("I THINK...")
for(int x : ans) {
cerr << x << ' ';
output(x);
}
cerr << '\n';
}
};
void decode(signed msz, signed N, signed xs[]) {
mydec(msz, N, xs);
}
Compilation message
encoder.cpp:165:6: warning: 'void {anonymous}::mydec(int, int, int*)' defined but not used [-Wunused-function]
165 | void mydec(signed msz, signed N, signed xs[]) {
| ^~~~~
decoder.cpp:125:9: warning: 'std::vector<long long int> {anonymous}::splay(std::vector<long long int>, long long int)' defined but not used [-Wunused-function]
125 | vt<int> splay(vt<int> co, int N) {
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
297 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
283 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
284 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
283 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
284 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Runtime error |
284 ms |
262144 KB |
Execution killed with signal 9 |
| 3 |
Runtime error |
288 ms |
262144 KB |
Execution killed with signal 9 |
| 4 |
Runtime error |
282 ms |
262144 KB |
Execution killed with signal 9 |
| 5 |
Runtime error |
295 ms |
262144 KB |
Execution killed with signal 9 |
| 6 |
Runtime error |
283 ms |
262144 KB |
Execution killed with signal 9 |
| 7 |
Runtime error |
285 ms |
262144 KB |
Execution killed with signal 9 |
