Submission #1154380

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154380		hiderr	Parrots (IOI11_parrots)	C++20	98 / 100	6 ms	840 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"

#include <bits/stdc++.h>
using namespace std;
#define loop(i, a, b) for(int i = a; i <= b; i++)
#define loop_rev(i, a, b) for(int i = a; i >= b; i--)
#define all(x) x.begin(), x.end()
#define sz(x) int(x.size())
#define eb emplace_back
#define pb push_back

using i128 = __int128_t;
static constexpr int DATA_BITS = 5;
static constexpr int ID_BITS = 3;
static constexpr int VEC_LEN = 5 << (DATA_BITS - 2);
static constexpr int GROUP_SIZE = (1 << (DATA_BITS - 2));
static constexpr i128 inf = (i128(1) << i128(70));
static constexpr int ALPH = (1 << DATA_BITS);
static vector<vector<i128>> dp;

static void calc_dp() {
  dp.resize(VEC_LEN + 1, vector<i128>(ALPH + 1, 0));
  dp[0][ALPH - 1] = 1;

  loop(len, 1, VEC_LEN) {
    loop_rev(x, ALPH - 1, 0) {
      dp[len][x] = dp[len][x + 1] + dp[len - 1][x];
      if(dp[len][x] > inf) {
        dp[len][x] = inf;
      }
    }
  }
}

vector<int> encode(i128 val) {
  vector<int> digits(VEC_LEN);
  int curr = 0, curr_len = (-1);
  loop(len, 1, VEC_LEN) {
    auto val2 = val;
    loop(x, 0, ALPH - 1) {
      if(val2 <= dp[len][x]) {
        digits[len - 1] = x;
        curr_len = len - 1;
        val = val2;
        curr = x;
        break;
      }
      else {
        val2 -= dp[len][x];
      }
    }
    if(curr_len != (-1)) {
      break;
    }
  }
  loop_rev(len, curr_len, 1) {
    loop(x, curr, ALPH - 1) {
      if(val <= dp[len][x]) {
        digits[len - 1] = x;
        curr = x;
        break;
      }
      else {
        val -= dp[len][x];
      }
    }
  }
  return digits;
}

void burn(i128 val, int id) {
  auto encoded = encode(val);
  loop(i, 0, VEC_LEN - 1) {
    int byte = 0;
    byte |= id;
    byte |= (encoded[i] << ID_BITS);
    send(byte);
  }
}

void encode(int n, int message[]) {
  calc_dp();
  loop(id, 0, (n + GROUP_SIZE - 1) / GROUP_SIZE - 1) {
    i128 val = 0, mul = 1;
    loop(i, 0, GROUP_SIZE - 1) {
      int byte_i = GROUP_SIZE * id + i;
      if(byte_i >= n) break;
      val |= mul * message[byte_i];
      mul <<= 8;
    }
    burn(val + 1, id);
  }
}

decoder

#include "decoder.h"
#include "decoderlib.h"

#include <bits/stdc++.h>
using namespace std;
#define loop(i, a, b) for(int i = a; i <= b; i++)
#define loop_rev(i, a, b) for(int i = a; i >= b; i--)
#define all(x) x.begin(), x.end()
#define sz(x) int(x.size())
#define eb emplace_back
#define pb push_back

using i128 = __int128_t;
static constexpr int DATA_BITS = 5;
static constexpr int ID_BITS = 3;
static constexpr int VEC_LEN = 5 << (DATA_BITS - 2);
static constexpr int GROUP_SIZE = (1 << (DATA_BITS - 2));
static constexpr i128 inf = (i128(1) << i128(70));
static constexpr int ALPH = (1 << DATA_BITS);
static vector<vector<i128>> dp;

static void calc_dp() {
  dp.resize(VEC_LEN + 1, vector<i128>(ALPH + 1, 0));
  dp[0][ALPH - 1] = 1;

  loop(len, 1, VEC_LEN) {
    loop_rev(x, ALPH - 1, 0) {
      dp[len][x] = dp[len][x + 1] + dp[len - 1][x];
      if(dp[len][x] > inf) {
        dp[len][x] = inf;
      }
    }
  }

}

i128 decode(vector<int> digits) {
  int curr = 0; i128 res = 0;
  loop_rev(len, VEC_LEN, 1) {
    loop(x, curr, digits[len - 1] - 1) {
      res += dp[len][x];
    }
    curr = digits[len - 1];
  }
  return res + 1;
}

void decode(int n, int l, int shuffled[]) {
  calc_dp();
  vector<vector<int>> codes(n);
  vector<int> ans;

  loop(i, 0, l - 1) {
    int id = shuffled[i] & ((1 << ID_BITS) - 1);
    int val = shuffled[i] / (1 << ID_BITS);
    codes[id].pb(val);
  }

  loop(id, 0, (n + GROUP_SIZE - 1) / GROUP_SIZE - 1) {
    sort(all(codes[id]), greater<int>());
    i128 value = decode(codes[id]) - 1;
    loop(i, 0, GROUP_SIZE - 1) {
      ans.pb(value & ((1 << 8) - 1));
      value >>= 8;
    }
  }

  loop(i, 0, n - 1) {
    output(ans[i]);
  }

}

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