Submission #191633

#	Time	Username	Problem	Language	Result	Execution time	Memory
191633		kdh9949	Parrots (IOI11_parrots)	C++17	100 / 100	283 ms	167704 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
#include <algorithm>
using namespace std;

static const int N = 256, M = 64;

struct BI_enc{
  int a[N], len;

  BI_enc(){
    len = 1;
    for(int i = 0; i < N; i++) a[i] = 0;
  }

  BI_enc(int n, int b[]){
    len = 1;
    for(int i = 0; i < n; i++){
      a[i] = b[i];
      if(a[i]) len = i + 1;
    }
  }

  BI_enc operator+(const BI_enc &o) const {
    BI_enc r;
    r.len = max(len, o.len);
    
    for(int i = 0, carry = 0; i < r.len; i++){
      r.a[i] = (a[i] + o.a[i] + carry) % N;
      carry = (a[i] + o.a[i] + carry) / N;
      if(r.len <= M && i == r.len - 1 && carry) r.a[r.len++] = 1;
    }

    return r;
  }

  bool operator<(const BI_enc &o) const {
    if(len != o.len) return (len < o.len);
    for(int i = len - 1; i >= 0; i--) if(a[i] != o.a[i]) return (a[i] < o.a[i]);
    return false;
  }
};

static BI_enc d[N + 1][5 * M + 1];
static int calced;

void calc_enc(int n){
  d[0][0].a[0] = 1;

  for(int i = 1; i <= N; i++){
    for(int j = 0; j <= 5 * n; j++){
      d[i][j] = d[i - 1][j];
      if(j) d[i][j] = d[i][j] + d[i][j - 1];
    }
  }
  calced = 1;
}

BI_enc num2cmb(BI_enc num, int n){
  BI_enc res, cur;
  int left = 5 * n;

  for(int i = 0; i < N; i++){
    while(left && !(num < cur + d[N - 1 - i][left])){
      cur = cur + d[N - 1 - i][left];
      res.a[i]++;
      left--;
    }
  }

  return res;
}

void encode(int n, int a[])
{
  if(!calced) calc_enc(n);
  
  BI_enc num(n, a);
  BI_enc cmb = num2cmb(num, n);
  
  for(int i = 0; i < N; i++) for(int j = 0; j < cmb.a[i]; j++) send(i);
}

decoder

#include "decoder.h"
#include "decoderlib.h"
#include <algorithm>
using namespace std;

static const int N = 256, M = 64;

struct BI_dec{
  int a[N], len;

  BI_dec(){
    len = 1;
    for(int i = 0; i < N; i++) a[i] = 0;
  }

  BI_dec operator+(const BI_dec &o) const {
    BI_dec r;
    r.len = max(len, o.len);
    
    for(int i = 0, carry = 0; i < r.len; i++){
      r.a[i] = (a[i] + o.a[i] + carry) % N;
      carry = (a[i] + o.a[i] + carry) / N;
      if(r.len <= M && i == r.len - 1 && carry) r.a[r.len++] = 1;
    }

    return r;
  }

  bool operator<(const BI_dec &o) const {
    if(len != o.len) return (len < o.len);
    for(int i = len - 1; i >= 0; i--) if(a[i] != o.a[i]) return (a[i] < o.a[i]);
    return false;
  }
};

static BI_dec d[N + 1][5 * M + 1];
static int calced;

void calc_dec(int n){
  d[0][0].a[0] = 1;

  for(int i = 1; i <= N; i++){
    for(int j = 0; j <= 5 * n; j++){
      d[i][j] = d[i - 1][j];
      if(j) d[i][j] = d[i][j] + d[i][j - 1];
    }
  }
  calced = 1;
}

BI_dec cmb2num(BI_dec cmb, int n){
  BI_dec res;
  int left = 5 * n;

  for(int i = 0; i < N; i++){
    for(int j = 0; j < cmb.a[i]; j++){
      res = res + d[N - 1 - i][left--];
    }
  }

  return res;
}

void decode(int n, int l, int x[])
{
  if(!calced) calc_dec(n);
  
  BI_dec cmb;
  for(int i = 0; i < l; i++) cmb.a[x[i]]++;
  BI_dec res = cmb2num(cmb, n);
  
  for(int i = 0; i < n; i++) output(res.a[i]);
}

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