Submission #1141157

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

encoder

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

using namespace std;

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 = 15; t2 >= 0; t2 --) {
      //cout << "num: " << t2 << " niv: " << t1 << " valor: " << f(t2, t1) << " Code: " << code << endl;
      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 = 0; niv < posi.size(); niv ++) {
    if (posi[niv].first <= code && code <= posi[niv].second) {
      code -= posi[niv].first;
      sendcode(code, niv, pre << 4, posi);
    }
  }
}

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

decoder

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

using namespace std;

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 <= 20; t1 ++) {
    posi.push_back({f(17, t1 - 1) - 1, f(17, t1 - 1) + f(16, t1) - 2});
  }
  for (int t1 = 0; t1 < t; t1++) {
    ns[t1] = cod[t1];
  }
  sort(ns.rbegin(), ns.rend());
  int sup = 16 - 1;
  int index = 0;
  while (n >= 4) {
    long long code = 0;
    vector<int> nums;
    while (index < t && sup == (ns[index] >> 4)) {
      nums.push_back(ns[index] % 16);
      index ++;
    }
    code = decod(nums) + posi[nums.size()].first;
    n -= 4;
    sup --;
    vector<int> ax1;
    for (int t1 = 4; 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] >> 4)) {
      nums.push_back(ns[index] % 16);
      index ++;
    }
    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: 0 / 17
• Subtask 3: 0 / 18
• Subtask 4: 0 / 29
• Subtask 5: 0 / 19