#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
struct BigInt{
ll a[20];
BigInt(){fill(a, a+20, 0);}
BigInt(ll x){a[0] = x; fill(a+1, a+20, 0);}
void print(char _end = 0){
char buf[360];
for (int i=0;i<20;i++){
ll tmp = a[i];
for (int j=0;j<18;j++){
buf[i*18+j] = tmp%10 + '0';
tmp /= 10;
}
}
bool flag = 0;
for (int i=359;i>=0;i--){
if (!flag){
if (buf[i]!='0') flag = 1;
else continue;
}
printf("%c", buf[i]);
}
if (!flag) printf("0");
if (_end) printf("%c", _end);
}
bool operator < (const BigInt &B) const{
for (int i=19;i>=0;i--){
if (a[i] < B.a[i]) return true;
else if (a[i] > B.a[i]) return false;
}
return false;
}
BigInt operator + (const BigInt &B) const{
BigInt ret = *this;
bool carry = 0;
for (int i=0;i<20;i++){
if (carry) ret.a[i]++;
ret.a[i] += B.a[i];
if (ret.a[i] >= INF) ret.a[i] -= INF, carry = 1;
else carry = 0;
}
assert(!carry);
//for (int i=0;i<20;i++) printf("%lld ", ret.a[i]);
//printf("\n");
return ret;
}
BigInt operator - (const BigInt &B) const{
BigInt ret = *this;
bool carry = 0;
for (int i=0;i<20;i++){
ll cur = B.a[i];
if (carry) cur++;
if (ret.a[i] < cur){
ret.a[i] += INF;
carry = 1;
}
else carry = 0;
ret.a[i] -= cur;
}
assert(!carry);
return ret;
}
};
static BigInt comb[601][601], pw[601];
static void init(){
if (comb[0][0].a[0]) return;
for (int i=0;i<=600;i++){
comb[i][0] = BigInt(1);
comb[i][i] = BigInt(1);
for (int j=1;j<i;j++) comb[i][j] = comb[i-1][j] + comb[i-1][j-1];
if (i) pw[i] = pw[i-1] + pw[i-1];
else pw[i] = BigInt(1);
}
//pw[600].print('\n');
//comb[600][300].print('\n');
//(pw[600]-comb[600][300]).print('\n');
}
static BigInt H(int n, int r){
return comb[n+r-1][r];
}
void encode(int N, int M[])
{
init();
BigInt _code;
for (int i=0;i<N;i++){
for (int j=0;j<8;j++) if (M[i]&(1<<j)){
_code = _code + pw[i*8+j];
}
}
//_code.print('\n');
int cur = 0;
for (int i=0;i<N*5;i++){
int rem = N*5-i-1;
while (!(_code < H(256-cur, rem))){
_code = _code - H(256-cur, rem);
cur++;
}
send(cur);
}
//printf("--\n");
}
#include "decoder.h"
#include "decoderlib.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
struct BigInt{
ll a[20];
BigInt(){fill(a, a+20, 0);}
BigInt(ll x){a[0] = x; fill(a+1, a+20, 0);}
void print(char _end = 0){
char buf[360];
for (int i=0;i<20;i++){
ll tmp = a[i];
for (int j=0;j<18;j++){
buf[i*18+j] = tmp%10 + '0';
tmp /= 10;
}
}
bool flag = 0;
for (int i=359;i>=0;i--){
if (!flag){
if (buf[i]!='0') flag = 1;
else continue;
}
printf("%c", buf[i]);
}
if (!flag) printf("0");
if (_end) printf("%c", _end);
}
bool operator < (const BigInt &B) const{
for (int i=19;i>=0;i--){
if (a[i] < B.a[i]) return true;
else if (a[i] > B.a[i]) return false;
}
return false;
}
BigInt operator + (const BigInt &B) const{
BigInt ret = *this;
bool carry = 0;
for (int i=0;i<20;i++){
if (carry) ret.a[i]++;
ret.a[i] += B.a[i];
if (ret.a[i] >= INF) ret.a[i] -= INF, carry = 1;
else carry = 0;
}
assert(!carry);
//for (int i=0;i<20;i++) printf("%lld ", ret.a[i]);
//printf("\n");
return ret;
}
BigInt operator - (const BigInt &B) const{
BigInt ret = *this;
bool carry = 0;
for (int i=0;i<20;i++){
ll cur = B.a[i];
if (carry) cur++;
if (ret.a[i] < cur){
ret.a[i] += INF;
carry = 1;
}
else carry = 0;
ret.a[i] -= cur;
}
assert(!carry);
return ret;
}
};
static BigInt comb[601][601], pw[601];
static void init(){
if (comb[0][0].a[0]) return;
for (int i=0;i<=600;i++){
comb[i][0] = BigInt(1);
comb[i][i] = BigInt(1);
for (int j=1;j<i;j++) comb[i][j] = comb[i-1][j] + comb[i-1][j-1];
if (i) pw[i] = pw[i-1] + pw[i-1];
else pw[i] = BigInt(1);
}
//pw[600].print('\n');
//comb[600][300].print('\n');
//(pw[600]-comb[600][300]).print('\n');
}
static BigInt H(int n, int r){
return comb[n+r-1][r];
}
static int a[1010];
void decode(int N, int L, int X[])
{
fill(a, a+N, 0);
init();
sort(X, X+L);
int cur = 0;
BigInt _code;
for (int i=0;i<L;i++){
int rem = L-i-1;
while(cur<X[i]){
_code = _code + H(256-cur, rem);
cur++;
}
}
int pt = N*8-1;
for (int i=N-1;i>=0;i--){
for (int j=7;j>=0;j--){
if (!(_code < pw[pt])){
_code = _code - pw[pt];
a[i] |= 1<<j;
}
pt--;
}
}
for (int i=0;i<N;i++) output(a[i]);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
71 ms |
113836 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
70 ms |
114200 KB |
Output is correct |
| 2 |
Correct |
75 ms |
114280 KB |
Output is correct |
| 3 |
Correct |
78 ms |
114372 KB |
Output is correct |
| 4 |
Correct |
72 ms |
114376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
71 ms |
114420 KB |
Output is correct |
| 2 |
Correct |
82 ms |
114248 KB |
Output is correct |
| 3 |
Correct |
71 ms |
114468 KB |
Output is correct |
| 4 |
Correct |
81 ms |
114292 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
73 ms |
114268 KB |
Output is correct |
| 2 |
Correct |
79 ms |
114336 KB |
Output is correct |
| 3 |
Correct |
70 ms |
114264 KB |
Output is correct |
| 4 |
Correct |
77 ms |
114264 KB |
Output is correct |
| 5 |
Correct |
74 ms |
114316 KB |
Output is correct |
| 6 |
Correct |
77 ms |
114308 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
75 ms |
114224 KB |
Output is correct - P = 5.000000 |
| 2 |
Correct |
79 ms |
114288 KB |
Output is correct - P = 5.000000 |
| 3 |
Correct |
82 ms |
114384 KB |
Output is correct - P = 5.000000 |
| 4 |
Correct |
74 ms |
114384 KB |
Output is correct - P = 5.000000 |
| 5 |
Correct |
83 ms |
114616 KB |
Output is correct - P = 5.000000 |
| 6 |
Correct |
81 ms |
114484 KB |
Output is correct - P = 5.000000 |
| 7 |
Correct |
84 ms |
114408 KB |
Output is correct - P = 5.000000 |
