#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>
using namespace std;
static const int base=1000000000;
static struct bignum{
vector <int> d;
}dp[301][301];
static bignum f(int x){
if (!x)
return {{0}};
bignum a;
for (;x;x/=base)
a.d.push_back(x%base);
return a;
}
static bool operator <(bignum a, bignum b){
while (a.d.size()<b.d.size())
a.d.push_back(0);
while (b.d.size()<a.d.size())
b.d.push_back(0);
for (int i=a.d.size()-1;i>=0;i--)
if (a.d[i]!=b.d[i])
return a.d[i]<b.d[i];
return false;
}
static bignum operator +(bignum a, bignum b){
bignum c;
if (a.d.size()>b.d.size())
swap(a,b);
while (a.d.size()<b.d.size())
a.d.push_back(0);
int carry=0;
for (int i=0;i<a.d.size();i++){
int x=a.d[i]+b.d[i]+carry;
c.d.push_back(x%base);
carry=x/base;
}
if (carry)
c.d.push_back(carry);
return c;
}
static bignum operator -(bignum a, bignum b){
bignum c;
while (a.d.size()>b.d.size())
b.d.push_back(0);
int carry=0;
for (int i=0;i<a.d.size();i++){
int x=a.d[i]-b.d[i]-carry;
if (x<0){
x+=base;
carry=1;
}
else
carry=0;
c.d.push_back(x);
}
return c;
}
static bignum operator *(bignum a, int b){
bignum c;
long long carry=0;
for (int i=0;i<a.d.size();i++){
long long x=1LL*a.d[i]*b+carry;
c.d.push_back(x%base);
carry=x/base;
}
for (;carry;carry/=base)
c.d.push_back(carry%base);
return c;
}
static bignum calc(int i, int j){
if (i<0)
return {{0}};
if (j<0)
return {{1}};
if (!dp[i][j].d.empty())
return dp[i][j];
return dp[i][j]=calc(i-1,j)+calc(i,j-1);
}
void encode(int N, int M[]){
bignum val={{0}};
for (int i=N-1;i>=0;i--)
val=val*256+f(M[i]);
int n=0,i=0;
while (calc(255,n)<val)
n++;
for (int j=0;j<=n;j++){
while (calc(255-i,n-j-1)-f(1)<val){
val=val-calc(255-i,n-j-1);
i++;
}
send(i);
}
}
#include "decoder.h"
#include "decoderlib.h"
#include <bits/stdc++.h>
using namespace std;
static const int base=1000000000;
static struct bignum{
vector <int> d;
}dp[301][301];
static bignum f(int x){
if (!x)
return {{0}};
bignum a;
for (;x;x/=base)
a.d.push_back(x%base);
return a;
}
static bignum operator +(bignum a, bignum b){
bignum c;
if (a.d.size()>b.d.size())
swap(a,b);
while (a.d.size()<b.d.size())
a.d.push_back(0);
int carry=0;
for (int i=0;i<a.d.size();i++){
int x=a.d[i]+b.d[i]+carry;
c.d.push_back(x%base);
carry=x/base;
}
if (carry)
c.d.push_back(carry);
return c;
}
static bignum operator -(bignum a, bignum b){
bignum c;
while (a.d.size()>b.d.size())
a.d.push_back(0);
int carry=0;
for (int i=0;i<a.d.size();i++){
int x=a.d[i]-b.d[i]-carry;
if (x<0){
x+=base;
carry=1;
}
c.d.push_back(x);
}
return c;
}
static pair <bignum, int> operator /(bignum a, int b){
bignum c;
int carry=0;
for (int i=a.d.size()-1;i>=0;i--){
long long x=1LL*carry*base+a.d[i];
if (x/b||!c.d.empty())
c.d.push_back(x/b);
carry=x%b;
}
reverse(c.d.begin(),c.d.end());
return {c,carry};
}
static bignum calc(int i, int j){
if (i<0||j<0)
return {{0}};
if (!i&&!j)
return {{1}};
if (!dp[i][j].d.empty())
return dp[i][j];
return dp[i][j]=calc(i-1,j)+calc(i,j-1);
}
void decode(int N, int L, int X[]){
sort(X,X+L);
bignum val={{0}};
for (int i=0;i<L;i++)
for (int j=(i?X[i-1]:0);j<X[i];j++)
val=val+calc(255-j,L-i-1);
while (N--){
auto [q,r]=val/256;
output(r);
val=q;
}
}
Compilation message
encoder.cpp: In function 'bignum operator+(bignum, bignum)':
encoder.cpp:34:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | for (int i=0;i<a.d.size();i++){
| ~^~~~~~~~~~~
encoder.cpp: In function 'bignum operator-(bignum, bignum)':
encoder.cpp:48:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for (int i=0;i<a.d.size();i++){
| ~^~~~~~~~~~~
encoder.cpp: In function 'bignum operator*(bignum, int)':
encoder.cpp:63:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for (int i=0;i<a.d.size();i++){
| ~^~~~~~~~~~~
decoder.cpp: In function 'bignum operator+(bignum, bignum)':
decoder.cpp:24:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | for (int i=0;i<a.d.size();i++){
| ~^~~~~~~~~~~
decoder.cpp: In function 'bignum operator-(bignum, bignum)':
decoder.cpp:38:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | for (int i=0;i<a.d.size();i++){
| ~^~~~~~~~~~~
decoder.cpp: At global scope:
decoder.cpp:33:15: warning: 'bignum operator-(bignum, bignum)' defined but not used [-Wunused-function]
33 | static bignum operator -(bignum a, bignum b){
| ^~~~~~~~
decoder.cpp:9:15: warning: 'bignum f(int)' defined but not used [-Wunused-function]
9 | static bignum f(int x){
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7440 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
7700 KB |
Output is correct |
2 |
Correct |
8 ms |
7960 KB |
Output is correct |
3 |
Correct |
10 ms |
7456 KB |
Output is correct |
4 |
Correct |
11 ms |
7448 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
7452 KB |
Output is correct |
2 |
Correct |
8 ms |
7448 KB |
Output is correct |
3 |
Correct |
10 ms |
7456 KB |
Output is correct |
4 |
Correct |
11 ms |
7696 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
7436 KB |
Output is correct |
2 |
Correct |
11 ms |
7456 KB |
Output is correct |
3 |
Correct |
13 ms |
7968 KB |
Output is correct |
4 |
Correct |
17 ms |
8480 KB |
Output is correct |
5 |
Correct |
17 ms |
8920 KB |
Output is correct |
6 |
Correct |
18 ms |
8484 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
7448 KB |
Output is correct - P = 1.750000 |
2 |
Correct |
18 ms |
8492 KB |
Output is correct - P = 2.437500 |
3 |
Correct |
20 ms |
9000 KB |
Output is correct - P = 2.484848 |
4 |
Correct |
30 ms |
11552 KB |
Output is correct - P = 3.300000 |
5 |
Correct |
41 ms |
13644 KB |
Output is correct - P = 3.850000 |
6 |
Correct |
44 ms |
14572 KB |
Output is correct - P = 4.031746 |
7 |
Correct |
59 ms |
15256 KB |
Output is correct - P = 4.093750 |