Submission #1141201

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141201		josephtenorio	Parrots (IOI11_parrots)	C++20	100 / 100	9 ms	840 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>

using namespace std;

int bits = 4;
int emp = 64 / pow(2, 8 - bits);
int pn = 5; 

map<int, map<int, long long>> dp;

long long f(int num, int niv) {
  if (niv == 0) return 1;
  if (niv == 1 || num == 0) {
    return num;
  }
  if (dp[num][niv] == 0) {
    dp[num][niv] = f(num, niv - 1) + f(num - 1, niv);
  }
  return dp[num][niv];
}

void sendcode(long long code, int niv, int pre, vector<pair<long long, long long>> &posi) {
  for (int t1 = niv; t1 >= 1; t1 --) {
    for (int t2 = (1<<bits)-1; t2 >= 0; t2 --) {
      if (code >= f(t2, t1)) {
        send(pre + t2);
        code -= f(t2, t1);
        break ;
      }
    }
  }
}

void empac(long long code, int pre, vector<pair<long long, long long>> &posi) {
  for (int niv = 1; niv < posi.size(); niv ++) {
    if (posi[niv].first <= code && code <= posi[niv].second) {
      code -= posi[niv].first;
      sendcode(code, niv, pre << bits, posi);
      break ;
    }
  }
}

void encode(int n, int m[]) {
  vector<pair<long long, long long>> posi = {{-1, -1}};
  for (int t1 = 1; t1 <= emp*pn; t1 ++) {
    posi.push_back({f((1<<bits)+1, t1 - 1) - 1, f((1<<bits)+1, t1 - 1) + f((1<<bits), t1) - 2});
  }
  int sup = (1<<(8-bits)) - 1;
  int index = 0;
  while (n >= emp) {
    long long code = 0;
    for (int t1 = 0; t1 < emp; t1 ++) {
      code <<= 8;
      code += m[index];
      index ++;
    }
    empac(code, sup, posi);
    n -= emp;
    sup --;
  }
  if (n != 0) {
    long long code = 0;
    for (int t1 = 0; t1 < n; t1 ++) {
      code <<= 8;
      code += m[index];
      index ++;
    }
    empac(code, sup, posi);
    sup --;
  }
  return ;
}

decoder

#include "decoder.h"
#include "decoderlib.h"
#include <bits/stdc++.h>

using namespace std;


int bits = 4;
int emp = 64 / pow(2, 8 - bits);
int pn = 5; 

map<int, map<int, long long>> dp;

long long f(int num, int niv) {
  if (niv == 0) return 1;
  if (niv == 1 || num == 0) {
    return num;
  }
  if (dp[num][niv] == 0) {
    dp[num][niv] = f(num, niv - 1) + f(num - 1, niv);
  }
  return dp[num][niv];
}

long long decod(vector<int> nums) {
  long long sum = 0;
  sort(nums.begin(), nums.end());
  for (int t1 = 0; t1 < nums.size(); t1 ++) {
    sum += f(nums[t1], t1+1);
  }
  return sum;
}

void decode(int n, int t, int cod[]) {
  vector<pair<long long, long long>> posi = {{-1, -1}};
  vector<int> ns(t);
  for (int t1 = 1; t1 <= emp*pn; t1 ++) {
    posi.push_back({f((1<<bits) + 1, t1 - 1) - 1, f((1<<bits) + 1, t1 - 1) + f((1<<bits), t1) - 2});
  }
  for (int t1 = 0; t1 < t; t1++) {
    ns[t1] = cod[t1];
  }
  sort(ns.rbegin(), ns.rend());
  int sup = (1<<(8-bits)) - 1;
  int index = 0;
  while (n >= emp) {
    long long code = 0;
    vector<int> nums;
    while (index < t && sup == (ns[index] >> bits)) {
      nums.push_back(ns[index] % (1<<bits));
      index ++;
    }
    code = decod(nums) + posi[nums.size()].first;
    n -= emp;
    sup --;
    vector<int> ax1;
    ax1.clear();
    for (int t1 = emp; t1 > 0; t1 --) {
      ax1.push_back(code % 256);
      code >>= 8;
    }
    for (int t1 = ax1.size() -1; t1 >= 0; t1 --) {
      output(ax1[t1]);
    }
  }
  if (n != 0) {
    long long code = 0;
    vector<int> nums;
    while (index < t && sup == (ns[index] >> bits)) {
      nums.push_back(ns[index] % (1<<bits));
      index ++;
    }
    code = decod(nums) + posi[nums.size()].first;
    vector<int> ax1;
    for (int t1 = n; t1 > 0; t1 --) {
      ax1.push_back(code % 256);
      code >>= 8;
    }
    for (int t1 = ax1.size() -1; t1 >= 0; t1 --) {
      output(ax1[t1]);
    }
  }
}

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