Submission #14844

#	Time	Username	Problem	Language	Result	Execution time	Memory
14844		minsu	Parrots (IOI11_parrots)	C++14	99 / 100	12 ms	2688 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long lld;

static const int R = 20;
static lld cache[R+1][R+1];
static bool chk;
static lld H(int n, int r){
  if(!chk){
    for(int i=0;i<=R;i++)
      for(int j=0;j<=R;j++)
        cache[i][j] = !j ? 1: !i ? 0 : cache[i-1][j]+cache[i][j-1];
    chk = 1;
  }
  return cache[n][r];
}

//     257 ** 4 = 4362470401L
// H ( 17, 20 ) = 7307872110L
void encode(int N, int M[])
{
  lld num = 0; vector<lld> packet;
  int n = (N+3)/4*4;
  for(int i=0; i<n; i++){
    num = num * 257 + ( i < N ? M[i] + 1 : 0 );
    if( i%4 == 3 ) { packet.push_back( num ); num=0; }
  }
  // _ 0 1 2 3 4 .. 15
  for(int i=0; i<packet.size(); i++){
    lld p = packet[i]; int r = R; p--;
    for(int j=1; j<=17; j++){
      int k;
      for(k = r; k>=0; k--){
        if( H(17-j, r-k) <= p ) p-= H(17-j, r-k);
        else break;
      } r-=k;
      while( (j-1) && k--) send(i*16 + j-2);
    }
  }
}

decoder

#include "decoder.h"
#include "decoderlib.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long lld;

static const int R = 20;
static lld cache[R+1][R+1];
static bool chk;
static lld H(int n, int r){
  if(!chk){
    for(int i=0;i<=R;i++)
      for(int j=0;j<=R;j++)
        cache[i][j] = !j ? 1: !i ? 0 : cache[i-1][j]+cache[i][j-1];
    chk = 1;
  }
  return cache[n][r];
}

static int cnt[16][17];
void decode(int N, int L, int X[])
{
  int n = 0;
  memset(cnt, 0, sizeof cnt);
  for(int i=0; i<L; i++){
    int x = X[i];
    cnt[x/16][x%16+1]++;
    cnt[x/16][0]--;
    n = max(n, x/16);
  }
  for(int i=0; i<=n; i++){
    lld num = 0LL; cnt[i][0]+=R;
    int r = R;
    for(int j=1; j<=17; j++){
      int k;
      for(k = r; k>cnt[i][j-1]; k--)
        num+= H(17-j, r-k);
      r-=k;
    } num++;
    vector<int> ans;
    while(num){
      ans.push_back(num%257);
      num/=257;
    }
    for(auto it = ans.rbegin(); it!= ans.rend(); ++it)
      if(*it!=0) output(*it-1);
  }
}

Compilation message (stderr)

encoder.cpp: In function 'void encode(int, int*)':
encoder.cpp:31:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<packet.size(); i++){
                ~^~~~~~~~~~~~~~

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