#include<bits/stdc++.h>
#include "encoder.h"
#include "encoderlib.h"
#define T rieajre
#define a djsiajd
#define b hidah
#define c jeiaj
#define d askdoaojksod
#define e hcjdkafa
#define i hnckhnfisda
#define j djsiajdsa
#define ii cxvcxvkn
#define jj vclkalkf
#define zx asjodoasjd
#define xc mlqwemqlewm
#define f dsmkzfmdkmrqw
#define K qwoeqweoiq
#define ans progprogpro
#define xr mremeraeormaeor
#define pas qwieoqiepsa
#define dp dpsdpsai
#define ZX ajojoejwqoe
#define ADD ADsfdjwoerfjwper
#define MUL dsakldmul
#define comp COmpwapewpqkewqe
#define eri lurjica
using namespace std;
int eri;
const long long T=1000000000000000000LL;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,f[1009],K;
vector <long long> xr[1009],pas,dp[1009][1009],ZX;
vector <long long> ADD(vector <long long> A, vector <long long> B){
int i=0;
long long zx=0;
vector <long long> ans;
while(1){
if(i<A.size()) zx+=A[i];
if(i<B.size()) zx+=B[i];
if(zx==0&&i>=max(A.size(),B.size())) break;
ans.push_back(zx%T);zx/=T;i++;
}
return ans;
}
bool comp(vector <long long> A, vector <long long> B){
if(A.size()<B.size()) return 1;
if(A.size()>B.size()) return 0;
int i=0;
for(i=A.size()-1; i>=0; i--){
if(A[i]<B[i]) return 1;
if(A[i]>B[i]) return 0;
}
return 1;
}
vector <long long> MUL(vector <long long> v, long long q){
vector <long long> qw;qw.push_back(0);
if(q==0) return qw;
if(q==1) return v;
qw=MUL(v,q/2);qw=ADD(qw,qw);
if(q%2==0) return qw; else return ADD(qw,v);
}
void encode(int NN, int MM[])
{
xr[0].clear();pas.clear();
a=NN;
for(i=1; i<=a; i++) f[i]=MM[i-1];
xr[0].push_back(1);
for(i=1; i<=a+1; i++){
xr[i]=MUL(xr[i-1],256);
}
pas.push_back(1);
for(i=1; i<=a; i++){
if(f[i]!=0) pas=ADD(pas,MUL(xr[i-1],f[i]));
}
K=a*5;
for(i=0; i<=K; i++){
for(j=0; j<=255; j++){
dp[i][j].clear();
if(i!=0) dp[i][j].push_back(0); else dp[i][j].push_back(1);
}
}
for(i=1; i<=K; i++){
for(j=0; j<=255; j++){
dp[i][j]=dp[i-1][j];
if(j!=0) dp[i][j]=ADD(dp[i][j],dp[i][j-1]);
}
}
ZX.clear();ZX.push_back(0);
//cout<<pas[0]<<" pas[0]\n";
for(i=K; i>=1; i--){
for(j=0; j<=255; j++){
if(comp(pas,ADD(ZX,dp[i][j]))==1){
break;
}
}
//if(j!=0) cout<<"i:"<<i<<" "<<ZX[0]<<" "<<dp[i][j-1][0]<<" "<<j<<"\n";
send(j);
if(j!=0) ZX=ADD(ZX,dp[i][j-1]);
}
}
#include<bits/stdc++.h>
#include "decoder.h"
#include "decoderlib.h"
using namespace std;
int eri;
const long long T=1000000000000000000LL;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,f[1009],K,ans[1009];
vector <long long> xr[1009],pas,dp[1009][1009],ZX,XC,CV;
vector <long long> ADD(vector <long long> A, vector <long long> B){
int i=0;
long long zx=0;
vector <long long> ans;
while(1){
if(i<A.size()) zx+=A[i];
if(i<B.size()) zx+=B[i];
if(zx==0&&i>=max(A.size(),B.size())) break;
ans.push_back(zx%T);zx/=T;i++;
}
return ans;
}
bool comp(vector <long long> A, vector <long long> B){
if(A.size()<B.size()) return 1;
if(A.size()>B.size()) return 0;
int i=0;
for(i=A.size()-1; i>=0; i--){
if(A[i]<B[i]) return 1;
if(A[i]>B[i]) return 0;
}
return 1;
}
vector <long long> MUL(vector <long long> v, long long q){
vector <long long> qw;qw.push_back(0);
if(q==0) return qw;
if(q==1) return v;
qw=MUL(v,q/2);qw=ADD(qw,qw);
if(q%2==0) return qw; else return ADD(qw,v);
}
void decode(int NN, int LL, int XX[])
{
/*int i, b;
for(i=0; i<L; i++) {
b = X[i];
output(b);
}*/
sort(XX,XX+LL);
xr[0].clear();pas.clear();
a=NN;
//for(i=1; i<=a; i++) f[i]=MM[i-1];
xr[0].push_back(1);
for(i=1; i<=a+1; i++){
xr[i]=MUL(xr[i-1],256);
}
K=a*5;
for(i=0; i<=K; i++){
for(j=0; j<=255; j++){
dp[i][j].clear();
if(i!=0) dp[i][j].push_back(0); else dp[i][j].push_back(1);
}
}
for(i=1; i<=K; i++){
for(j=0; j<=255; j++){
dp[i][j]=dp[i-1][j];
if(j!=0) dp[i][j]=ADD(dp[i][j],dp[i][j-1]);
}
}
pas.clear();
pas.push_back(1);
for(i=LL; i>=1; i--){
c=XX[i-1];
//cout<<c<<" i "<<i<<"\n";
if(c!=0) pas=ADD(pas,dp[i][c-1]);
}
//cout<<pas[0]<<"\n";
ZX.clear();ZX.push_back(0);
for(i=a; i>=1; i--){
XC.clear();XC.push_back(0);
for(j=0; j<=255; j++){
CV=XC;
XC=ADD(XC,xr[i-1]);
if(comp(pas,ADD(ZX,XC))==1){
break;
}
}
ans[i]=j;
if(j!=0) ZX=ADD(ZX,/*dp[i][j-1]*/CV);
}
for(i=1; i<=a; i++) output(ans[i]);
}
Compilation message
encoder.cpp: In function 'std::vector<long long int> ADsfdjwoerfjwper(std::vector<long long int>, std::vector<long long int>)':
encoder.cpp:37:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | if(i<A.size()) zx+=A[i];
| ^
encoder.cpp:38:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | if(i<B.size()) zx+=B[i];
| ^
encoder.cpp:39:16: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
39 | if(zx==0&&i>=max(A.size(),B.size())) break;
| ^
decoder.cpp: In function 'std::vector<long long int> ADD(std::vector<long long int>, std::vector<long long int>)':
decoder.cpp:14:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
14 | if(i<A.size()) zx+=A[i];
| ~^~~~~~~~~
decoder.cpp:15:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
15 | if(i<B.size()) zx+=B[i];
| ~^~~~~~~~~
decoder.cpp:16:16: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
16 | if(zx==0&&i>=max(A.size(),B.size())) break;
| ~^~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
49 ms |
49256 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
139 ms |
49652 KB |
Output is correct |
2 |
Correct |
195 ms |
50076 KB |
Output is correct |
3 |
Correct |
267 ms |
50372 KB |
Output is correct |
4 |
Correct |
300 ms |
50568 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
136 ms |
49584 KB |
Output is correct |
2 |
Correct |
199 ms |
49996 KB |
Output is correct |
3 |
Correct |
275 ms |
50644 KB |
Output is correct |
4 |
Correct |
289 ms |
50532 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
141 ms |
49728 KB |
Output is correct |
2 |
Correct |
290 ms |
50504 KB |
Output is correct |
3 |
Correct |
391 ms |
51124 KB |
Output is correct |
4 |
Correct |
609 ms |
52636 KB |
Output is correct |
5 |
Correct |
644 ms |
52952 KB |
Output is correct |
6 |
Correct |
767 ms |
52944 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
297 ms |
50692 KB |
Output is correct - P = 5.000000 |
2 |
Correct |
677 ms |
53060 KB |
Output is correct - P = 5.000000 |
3 |
Correct |
685 ms |
53280 KB |
Output is correct - P = 5.000000 |
4 |
Correct |
1150 ms |
56260 KB |
Output is correct - P = 5.000000 |
5 |
Correct |
1460 ms |
58420 KB |
Output is correct - P = 5.000000 |
6 |
Correct |
1655 ms |
58952 KB |
Output is correct - P = 5.000000 |
7 |
Correct |
1628 ms |
59140 KB |
Output is correct - P = 5.000000 |