Submission #515983

#	Time	Username	Problem	Language	Result	Execution time	Memory
515983		600Mihnea	Parrots (IOI11_parrots)	C++17	100 / 100	9 ms	1352 KiB

encoder

#pragma once
#include "encoder.h"
#include "encoderlib.h"

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;


void encode(int n, int __message[]) {

  const ll INF = (ll) 1e18;
  int CNT[4] = {5, 10, 15, 20};

  int START[4];
  for (int i = 0; i < 4; i++) {
    START[i] = CNT[i] + 15;
  }

  vector<vector<ll>> comb(100, vector<ll> (100, 0));
  for (int i = 0; i < 100; i++) {
    comb[i][0] = 1;
    for (int j = 1; j <= i; j++) {
      comb[i][j] = min(INF, comb[i - 1][j] + comb[i - 1][j - 1]);
    }
  }

  function<ll(int)> getvalue = [&] (int i) {
    if (0 <= i && i < n) {
      return __message[i];
    }
    return 0;
  };

  function<vector<int>(int, int, ll)> write = [&] (int CNT, int START, ll x) {
    vector<int> sol;
    int j = CNT;
    for (int i = START; i >= 0 && j >= 1; i--) {
      ll current = comb[i][j];
      if (x >= current) {
        x -= current;
        sol.push_back(START - i - (int) sol.size());
        j--;
      }
    }
    assert((int) sol.size() == CNT);
    assert(x == 0);
    return sol;
  };

  for (int l = 0; l < n; l += 4) {
    int k = min(4, n - l) - 1;
    ll num = getvalue(l) + getvalue(l + 1) * 256 + getvalue(l + 2) * 256 * 256 + getvalue(l + 3) * 256 * 256 * 256;
    vector<int> guys = write(CNT[k], START[k], num);
    for (auto &x : guys) {
      assert(0 <= x && x <= 16);
      if (x == 16) {
        continue;
      }
      send((l / 4) * 16 + x);
    }
  }
}

decoder

#pragma once
#include "decoder.h"
#include "decoderlib.h"

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

void decode(int n, int L, int guys[]) {

  const ll INF = (ll) 1e18;
  int CNT[4] = {5, 10, 15, 20};

  int START[4];
  for (int i = 0; i < 4; i++) {
    START[i] = CNT[i] + 15;
  }

  vector<vector<ll>> comb(100, vector<ll> (100, 0));
  for (int i = 0; i < 100; i++) {
    comb[i][0] = 1;
    for (int j = 1; j <= i; j++) {
      comb[i][j] = min(INF, comb[i - 1][j] + comb[i - 1][j - 1]);
    }
  }

  function<vector<int>(int, int, ll)> write = [&] (int CNT, int START, ll x) {
    vector<int> sol;
    int j = CNT;
    for (int i = START; i >= 0 && j >= 1; i--) {
      ll current = comb[i][j];
      if (x >= current) {
        x -= current;
        sol.push_back(START - i - (int) sol.size());
        j--;
      }
    }
    assert((int) sol.size() == CNT);
    assert(x == 0);
    return sol;
  };


  sort(guys, guys + L);

  int top = 0;

  for (int l = 0; l < n; l += 4) {
    int k = min(4, n - l) - 1;
    vector<int> inds;

    for (int j = 0; j < CNT[k]; j++) {
      int val;
      if (top < L && guys[top] / 16 == l / 4) {

        val = guys[top++] % 16;
      } else {
        val = 16;
      }
      int i = START[k] - j - val;
      inds.push_back(i);
    }
    sort(inds.begin(), inds.end());
    int j = CNT[k];
    ll num = 0;
    for (int i = START[k]; i >= 0 && j >= 1; i--) {
      ll current = comb[i][j];
      assert(!inds.empty());
      if (i == inds.back()) {
        inds.pop_back();
        num += current;
        j--;
      }
    }

    vector<ll> sol;
    sol.push_back(num % 256), num /= 256;
    sol.push_back(num % 256), num /= 256;
    sol.push_back(num % 256), num /= 256;
    sol.push_back(num % 256), num /= 256;

    sol.resize(k + 1);

    for (auto &x : sol) {
      output(x);
    }
  }
}

Compilation message (stderr)

encoder.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

decoder.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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