#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>
using namespace std;
const int C = 160;
const int B = 256;
const int N = 5 * 64;
struct NumBig {
int d[C];
void init() { for (int i = 0; i < C; i++) d[i] = 0; }
NumBig() { init(); }
void print() {
for (int i = 0; i < 50; i++) {
printf("%d ", d[i]);
}
printf("\n");
}
};
NumBig const operator + (NumBig a, NumBig b) {
NumBig res;
res.d[C - 1] = -1e9;
for (int i = 0; i < C; i++) {
res.d[i] += a.d[i] + b.d[i];
while (res.d[i] >= 10) {
res.d[i] -= 10;
res.d[i + 1] += 1;
}
}
res.d[C - 1] = 0;
return res;
}
NumBig const operator * (NumBig a, int c) {
//printf("mnozim sa %d\n", c);
NumBig res;
res.d[C - 1] = -1e9;
for (int i = 0; i < C; i++) {
res.d[i] += a.d[i] * c;
while (res.d[i] >= 10) {
res.d[i] -= 10;
res.d[i + 1] += 1;
}
}
res.d[C - 1] = 0;
return res;
}
bool const operator >= (NumBig a, NumBig b) {
for (int i = C - 1; i >= 0; i--) {
if (a.d[i] != b.d[i]) {
return a.d[i] > b.d[i];
}
}
return true;
}
NumBig const operator - (NumBig a, NumBig b) {
NumBig res;
for (int i = 0; i < C; i++) {
res.d[i] = a.d[i] - b.d[i];
while (res.d[i] < 0) {
res.d[i] += 10;
a.d[i + 1] -= 1;
}
}
return res;
}
NumBig pd[N][B];
void dp_make(int n) {
for (int i = 0; i < B; i++) {
pd[n - 1][i].init();
pd[n - 1][i].d[0] = 1;
}
for (int i = n - 2; i >= 0; i--) {
NumBig sum;
for (int j = B - 1; j >= 0; j--) {
sum = sum + pd[i + 1][j];
pd[i][j] = sum;
}
}
}
void encode(int N, int M[])
{
if (pd[N - 1][0].d[0] == 0)
dp_make(5 * N);
NumBig val, pw;
pw.d[0] = 1;
for (int i = 0; i < N; i++) {
val = val + (pw * M[i]);
pw = pw * B;
}
NumBig ONE;
ONE.d[0] = 1;
val = val + ONE;
int lst = 0;
NumBig cur_sum;
for (int i = 0; i < 5 * N; i++) {
for (int j = lst; j < B; j++) {
if (pd[i][j] >= val) {
lst = j;
send(lst);
break;
}
val = val - pd[i][j];
}
}
}
/*
8
1 0 1 0 0 1 1 0
*/
#include "decoder.h"
#include "decoderlib.h"
#include <bits/stdc++.h>
using namespace std;
const int C = 160;
const int B = 256;
const int N = 5 * 64;
struct BigNum {
int d[C];
void init() { for (int i = 0; i < C; i++) d[i] = 0; }
BigNum() { init(); }
void print() {
for (int i = 0; i < 50; i++) {
printf("%d ", d[i]);
}
printf("\n");
}
};
BigNum const operator + (BigNum a, BigNum b) {
BigNum res;
res.d[C - 1] = -1e9;
for (int i = 0; i < C; i++) {
res.d[i] += a.d[i] + b.d[i];
while (res.d[i] >= 10) {
res.d[i] -= 10;
res.d[i + 1] += 1;
}
}
res.d[C - 1] = 0;
return res;
}
BigNum const operator * (BigNum a, int c) {
// printf("mnozim sa %d\n", c);
BigNum res;
res.d[C - 1] = -1e9;
for (int i = 0; i < C; i++) {
res.d[i] += a.d[i] * c;
while (res.d[i] >= 10) {
res.d[i] -= 10;
res.d[i + 1] += 1;
}
}
res.d[C - 1] = 0;
return res;
}
bool const operator >= (BigNum a, BigNum b) {
for (int i = C - 1; i >= 0; i--) {
if (a.d[i] != b.d[i]) {
return a.d[i] > b.d[i];
}
}
return true;
}
BigNum const operator - (BigNum a, BigNum b) {
BigNum res;
for (int i = 0; i < C; i++) {
res.d[i] = a.d[i] - b.d[i];
while (res.d[i] < 0) {
res.d[i] += 10;
a.d[i + 1] -= 1;
}
}
return res;
}
BigNum dp[N][B];
void make_dp(int n) {
for (int i = 0; i < B; i++) {
dp[n - 1][i].init();
dp[n - 1][i].d[0] = 1;
}
for (int i = n - 2; i >= 0; i--) {
BigNum sum;
for (int j = B - 1; j >= 0; j--) {
sum = sum + dp[i + 1][j];
dp[i][j] = sum;
}
}
}
BigNum bpw[N];
void decode(int N, int L, int X[])
{
sort(X, X + L);
// printf("got decode seq = ");
// for (int i = 0; i < L; i++)
// printf("%d ", X[i]);
// printf("\n");
if (dp[L - 1][0].d[0] == 0)
make_dp(L);
BigNum val;
int lst = 0;
for (int i = 0; i < L; i++) {
while (lst != X[i]) {
val = val + dp[i][lst];
lst += 1;
}
}
bpw[0].d[0] = 1;
for (int i = 1; i < N; i++) {
bpw[i] = bpw[i - 1] * B;
}
// printf("SEQ VAL = ");
// val.print();
vector<int> ans;
for (int i = N - 1; i >= 0; i--) {
ans.push_back(0);
BigNum nm = bpw[i];
while (val >= nm) {
ans.back() += 1;
nm = nm + bpw[i];
}
nm = nm - bpw[i];
val = val - nm;
}
reverse(ans.begin(), ans.end());
for (int x : ans)
output(x);
// int i, b;
// for(i=0; i<L; i++) {
// b = X[i];
// output(b);
// }
}
/*
8
1 0 1 0 0 1 1 0
10
1 1 2 1 2 3 1 7 10 9
*/
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
44 ms |
103624 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
77 ms |
103796 KB |
Output is correct |
| 2 |
Correct |
85 ms |
103936 KB |
Output is correct |
| 3 |
Correct |
113 ms |
103980 KB |
Output is correct |
| 4 |
Correct |
109 ms |
103956 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
71 ms |
103976 KB |
Output is correct |
| 2 |
Correct |
86 ms |
103860 KB |
Output is correct |
| 3 |
Correct |
112 ms |
103728 KB |
Output is correct |
| 4 |
Correct |
113 ms |
103888 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
72 ms |
103888 KB |
Output is correct |
| 2 |
Correct |
109 ms |
104008 KB |
Output is correct |
| 3 |
Correct |
135 ms |
103832 KB |
Output is correct |
| 4 |
Correct |
1306 ms |
103924 KB |
Output is correct |
| 5 |
Correct |
1387 ms |
104196 KB |
Output is correct |
| 6 |
Correct |
223 ms |
103824 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
111 ms |
103824 KB |
Output is correct - P = 5.000000 |
| 2 |
Correct |
221 ms |
103912 KB |
Output is correct - P = 5.000000 |
| 3 |
Correct |
217 ms |
103972 KB |
Output is correct - P = 5.000000 |
| 4 |
Correct |
363 ms |
104012 KB |
Output is correct - P = 5.000000 |
| 5 |
Correct |
443 ms |
104000 KB |
Output is correct - P = 5.000000 |
| 6 |
Correct |
472 ms |
103976 KB |
Output is correct - P = 5.000000 |
| 7 |
Correct |
510 ms |
103940 KB |
Output is correct - P = 5.000000 |
