Submission #92175

#	Time	Username	Problem	Language	Result	Execution time	Memory
92175		Bodo171	Parrots (IOI11_parrots)	C++14	100 / 100	1564 ms	44336 KiB

encoder

#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();
}

decoder

#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 (stderr)

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];
            ^~~~

• Subtask 1: 17 / 17
• Subtask 2: 17 / 17
• Subtask 3: 18 / 18
• Subtask 4: 29 / 29
• Subtask 5: 19 / 19