This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>
using namespace std;
const int BASE = 31622;
const int LEN = 325;
struct BIGNUM {
vector<int> d;
}dp[LEN][256];
BIGNUM add(const BIGNUM& A, const BIGNUM& B) {
BIGNUM res;
int C = 0;
for(int i = 0; i < max((int)A.d.size(), (int)B.d.size()) || C; ++i) {
int cur = C;
if(i < (int)A.d.size()) cur += A.d[i];
if(i < (int)B.d.size()) cur += B.d[i];
C = cur >= BASE;
if(C) cur -= BASE;
res.d.push_back(cur);
}
return res;
}
BIGNUM sub(BIGNUM A, const BIGNUM& B) {
int C = 0;
for(int i = 0; i < (int)B.d.size() || C; ++i) {
A.d[i] -= C + (i < (int)B.d.size() ? B.d[i] : 0);
C = A.d[i] < 0;
if(C) A.d[i] += BASE;
}
while((int)A.d.size() && A.d.back() == 0) A.d.pop_back();
return A;
}
BIGNUM mul(const int& A, const BIGNUM& B) {
BIGNUM res;
int C = 0;
for(int i = 0; i < (int)B.d.size() || C; ++i) {
int cur = C;
if(i < (int)B.d.size()) cur += A * B.d[i];
C = cur / BASE;
res.d.push_back(cur - C * BASE);
}
while((int)res.d.size() && res.d.back() == 0) res.d.pop_back();
return res;
}
bool cmp(const BIGNUM& A, const BIGNUM& B) {
if((int)A.d.size() != (int)B.d.size()) return (int)A.d.size() < (int)B.d.size();
for(int i = (int)A.d.size() - 1; i >= 0; --i) {
if(A.d[i] != B.d[i]) return A.d[i] < B.d[i];
}
return 0;
}
void encode(int N, int M[]) {
for(int i = 0; i < 256; ++i) dp[0][i].d = {1};// ONE
for(int i = 1; i < LEN; ++i) dp[i][0].d = {1};// ONE
for(int i = 1; i < LEN; ++i) {
for(int j = 1; j < 256; ++j) {
dp[i][j] = add(dp[i][j - 1], dp[i - 1][j]);
}
}
BIGNUM val, pwi;
pwi.d = {1};
for(int i = N - 1; i >= 0; --i) {
val = add(val, mul(M[i], pwi));
if(i > 0) pwi = mul(256, pwi);
}
for(int i = LEN - 1; i >= 0; --i) {
int j;
for(j = 0; j < 256; ++j) {
if(cmp(val, dp[i][j])) {
break;
}
val = sub(val, dp[i][j]);
}
send(j);
}
}
#include "decoder.h"
#include "decoderlib.h"
#include <bits/stdc++.h>
using namespace std;
const int BASE = 31622;
const int LEN = 325;
struct BIGNUM {
vector<int> d;
}dp[LEN][256];
BIGNUM add(const BIGNUM& A, const BIGNUM& B) {
BIGNUM res;
int C = 0;
for(int i = 0; i < max((int)A.d.size(), (int)B.d.size()) || C; ++i) {
int cur = C;
if(i < (int)A.d.size()) cur += A.d[i];
if(i < (int)B.d.size()) cur += B.d[i];
C = cur >= BASE;
if(C) cur -= BASE;
res.d.push_back(cur);
}
return res;
}
BIGNUM sub(BIGNUM A, const BIGNUM& B) {
int C = 0;
for(int i = 0; i < (int)B.d.size() || C; ++i) {
A.d[i] -= C + (i < (int)B.d.size() ? B.d[i] : 0);
C = A.d[i] < 0;
if(C) A.d[i] += BASE;
}
while((int)A.d.size() && A.d.back() == 0) A.d.pop_back();
return A;
}
BIGNUM mul(const int& A, const BIGNUM& B) {
BIGNUM res;
int C = 0;
for(int i = 0; i < (int)B.d.size() || C; ++i) {
int cur = C;
if(i < (int)B.d.size()) cur += A * B.d[i];
C = cur / BASE;
res.d.push_back(cur - C * BASE);
}
while((int)res.d.size() && res.d.back() == 0) res.d.pop_back();
return res;
}
bool cmp(const BIGNUM& A, const BIGNUM& B) {
if((int)A.d.size() != (int)B.d.size()) return (int)A.d.size() < (int)B.d.size();
for(int i = (int)A.d.size() - 1; i >= 0; --i) {
if(A.d[i] != B.d[i]) return A.d[i] < B.d[i];
}
return 0;
}
void decode(int N, int L, int X[]) {
sort(X, X + L);
for(int i = 0; i < 256; ++i) dp[0][i].d = {1};// ONE
for(int i = 1; i < LEN; ++i) dp[i][0].d = {1};// ONE
for(int i = 1; i < LEN; ++i) {
for(int j = 1; j < 256; ++j) {
dp[i][j] = add(dp[i][j - 1], dp[i - 1][j]);
}
}
BIGNUM val;
for(int i = LEN - 1; i >= 0; --i) {
for(int j = 0; j < X[i]; ++j) val = add(val, dp[i][j]);
}
vector<BIGNUM> p(N);
p[0].d = {1};
for(int i = 1; i < N; ++i) {
p[i] = mul(256, p[i - 1]);
}
for(int i = N - 1; i >= 0; --i) {
int L = 0, R = 255;
while(L < R) {
int M = (L + R + 1) / 2;
if(cmp(val, mul(M, p[i]))) {
R = M - 1;
} else {
L = M;
}
}
output(L);
val = sub(val, mul(L, p[i]));
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |