#include "encoder.h"
#include "encoderlib.h"
#include <iostream>
using namespace std;
const int base=(1<<24);
const int nm=325,mm=275,cifmax=30;
static int dp[nm][mm][cifmax],sum[nm][mm][cifmax];
static int cost[cifmax],A[cifmax],aux[cifmax];
static int unu[cifmax],zr[cifmax];
static int v[nm];
static int i,j,poz,p,n,m,k;
void add(int A[],int B[])
{
A[0]=max(A[0],B[0]);
for(int idx=1;idx<=A[0];idx++)
{
A[idx]+=B[idx];
if(A[idx]>=base)
{
A[idx+1]+=(A[idx]>>24);
if(idx+1>A[0])
A[0]=idx+1;
A[idx]&=(base-1);
}
}
}
void memc(int A[],int B[])
{
for(int idx=1;idx<=A[0];idx++)
A[idx]=0;
A[0]=0;
for(int idx=0;idx<=B[0];idx++)
A[idx]=B[idx];
}
void prc_dp()
{
for(k=0;k<cifmax;k++)
unu[k]=zr[k]=0;
for(i=0;i<=n+1;i++)
for(j=0;j<=m+1;j++)
for(k=0;k<cifmax;k++)
dp[i][j][k]=sum[i][j][k]=0;
unu[0]=unu[1]=1;
for(i=n;i>=1;i--)
for(j=m;j>=0;j--)
{
add(dp[i][j],sum[i+1][j]);
if(i==n)
add(dp[i][j],unu);
add(sum[i][j],sum[i][j+1]);
add(sum[i][j],dp[i][j]);
}
}
bool mmic(int X[],int Y[])
{
if(X[0]<Y[0]) return 1;
if(X[0]>Y[0]) return 0;
for(int idx=X[0];idx>=1;idx--)
{
if(X[idx]<Y[idx]) return 1;
if(X[idx]>Y[idx]) return 0;
}
return 0;
}
void get_kth()
{
memc(cost,zr);memc(aux,zr);
for(poz=1;poz<=n;poz++)
{
p=v[poz-1];
memc(aux,cost);
for(int ok=1;ok!=0;)
{
add(aux,dp[poz][p]);
if(mmic(aux,A)) memc(cost,aux);
else v[poz]=p,ok=0;
p++;
}
send(v[poz]);
}
}
void encode(int N, int M[])
{
n=5*N;
m=255;
memc(A,zr);
int p;
for(i=0;i<N;i+=3)
{
p=i/3+1;
A[p]+=M[i];
if(i+1<N)A[p]+=(M[i+1]<<8);
if(i+2<N)A[p]+=(M[i+2]<<16);
if(A[p]) A[0]=p;
}
prc_dp();
add(A,unu);
get_kth();
}
#include "decoder.h"
#include "decoderlib.h"
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int base=(1<<24);
const int nm=325,mm=265,cifmax=30;
static int dp[nm][mm][cifmax],sum[nm][mm][cifmax+5];
static int cost[cifmax+5],A[cifmax+5],aux[cifmax+5],afis[5*cifmax];
static int unu[cifmax],zr[cifmax];
static int v[nm];
static int i,j,poz,p,n,m,k;
void adds(int A[],int B[])
{
A[0]=max(A[0],B[0]);
for(int idx=1;idx<=A[0];idx++)
{
A[idx]+=B[idx];
if(A[idx]>=base)
{
A[idx+1]+=(A[idx]>>24);
if(idx+1>A[0])
A[0]=idx+1;
A[idx]&=(base-1);
}
}
}
void memcs(int A[],int B[])
{
for(int idx=1;idx<=A[0];idx++)
A[idx]=0;
A[0]=0;
for(int idx=0;idx<=B[0];idx++)
A[idx]=B[idx];
}
void prc_dps()
{
for(k=0;k<cifmax;k++)
unu[k]=zr[k]=0;
for(i=0;i<=n+1;i++)
for(j=0;j<=m+1;j++)
for(k=0;k<cifmax;k++)
dp[i][j][k]=sum[i][j][k]=0;
unu[0]=unu[1]=1;
for(i=n;i>=1;i--)
for(j=m;j>=0;j--)
{
adds(dp[i][j],sum[i+1][j]);
if(i==n)
adds(dp[i][j],unu);
adds(sum[i][j],sum[i][j+1]);
adds(sum[i][j],dp[i][j]);
}
}
void getk()
{
memcs(A,zr);
for(i=1;i<=n;i++)
{
for(j=v[i-1];j<v[i];j++)
adds(A,dp[i][j]);
}
}
/*int cc(int A,int B)
{
long double f=0,I;
for(i=1;i<=A;i++)
{
I=i;
I=log2(I);
f+=I;
}
for(i=1;i<=B;i++)
{
I=i;
I=log2(I);
f-=I;
}
for(i=1;i<=A-B;i++)
{
I=i;
I=log2(I);
f-=I;
}
f=(int)ceil(f);
return (int) f;
}
void get_opt()
{
for(int ii=16;ii<=64;ii++)
{
cout<<8*ii-cc(256+5*ii-1,5*ii-1)<<' '<<(8*ii<=cc(256+5*ii-1,5*ii))<<'\n';
}
}*/
void decode(int N, int L, int X[])
{
int i, b;
n=5*N;
m=255;
for(i=0; i<L; i++) {
v[i+1] = X[i];
}
sort(v+1,v+L+1);
prc_dps();
getk();
//get_opt();
for(i=1;i<=N/3+3;i++)
{
afis[(i-1)*3+1]=(A[i]&((1<<8)-1));
afis[(i-1)*3+2]=((A[i]>>8)&((1<<8)-1));
afis[(i-1)*3+3]=(A[i]>>16);
}
for(i=1;i<=N;i++)
output(afis[i]);
}
Compilation message
decoder.cpp: In function 'void decode(int, int, int*)':
decoder.cpp:99:10: warning: unused variable 'b' [-Wunused-variable]
int i, b;
^
decoder.cpp: At global scope:
decoder.cpp:13:20: warning: 'p' defined but not used [-Wunused-variable]
static int i,j,poz,p,n,m,k;
^
decoder.cpp:13:16: warning: 'poz' defined but not used [-Wunused-variable]
static int i,j,poz,p,n,m,k;
^~~
decoder.cpp:10:39: warning: 'aux' defined but not used [-Wunused-variable]
static int cost[cifmax+5],A[cifmax+5],aux[cifmax+5],afis[5*cifmax];
^~~
decoder.cpp:10:12: warning: 'cost' defined but not used [-Wunused-variable]
static int cost[cifmax+5],A[cifmax+5],aux[cifmax+5],afis[5*cifmax];
^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
25 ms |
6392 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
96 ms |
6904 KB |
Output is correct |
| 2 |
Correct |
143 ms |
8984 KB |
Output is correct |
| 3 |
Correct |
207 ms |
11608 KB |
Output is correct |
| 4 |
Correct |
224 ms |
12300 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
94 ms |
6896 KB |
Output is correct |
| 2 |
Correct |
137 ms |
8888 KB |
Output is correct |
| 3 |
Correct |
205 ms |
11448 KB |
Output is correct |
| 4 |
Correct |
228 ms |
12160 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
96 ms |
6900 KB |
Output is correct |
| 2 |
Correct |
225 ms |
12284 KB |
Output is correct |
| 3 |
Correct |
308 ms |
14952 KB |
Output is correct |
| 4 |
Correct |
533 ms |
21364 KB |
Output is correct |
| 5 |
Correct |
567 ms |
22180 KB |
Output is correct |
| 6 |
Correct |
601 ms |
23092 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
230 ms |
12016 KB |
Output is correct - P = 5.000000 |
| 2 |
Correct |
583 ms |
22816 KB |
Output is correct - P = 5.000000 |
| 3 |
Correct |
600 ms |
23536 KB |
Output is correct - P = 5.000000 |
| 4 |
Correct |
1124 ms |
34608 KB |
Output is correct - P = 5.000000 |
| 5 |
Correct |
1452 ms |
41500 KB |
Output is correct - P = 5.000000 |
| 6 |
Correct |
1564 ms |
43420 KB |
Output is correct - P = 5.000000 |
| 7 |
Correct |
1540 ms |
44336 KB |
Output is correct - P = 5.000000 |
