Submission #103760

#	Time	Username	Problem	Language	Result	Execution time	Memory
103760		wxh010910	Parrots (IOI11_parrots)	C++17	100 / 100	13 ms	1792 KiB

encoder

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

using namespace std;

void encode(int N, int M[]) {
  vector<vector<long long>> dp(21, vector<long long>(16));
  for (int i = 0; i < 16; ++i) {
    dp[0][i] = 1;
  }
  for (int i = 1; i < 21; ++i) {
    for (int j = 0; j < 16; ++j) {
      for (int k = j; k < 16; ++k) {
        dp[i][j] += dp[i - 1][k];
      }
    }
  }
  vector<long long> sum(21);
  for (int i = 1; i < 21; ++i) {
    sum[i] = sum[i - 1] + dp[i][0];
  }
  vector<int> a(M, M + N);
  while (a.size() % 4) {
    a.push_back(0);
    ++N;
  }
  for (int i = 0; i < N; i += 4) {
    long long state = 0;
    for (int j = 0; j < 4; ++j) {
      state |= (long long) a[i + j] << (j * 8);
    }
    int len = 0;
    while (state >= sum[len]) {
      ++len;
    }
    state -= sum[len - 1];
    int last = 0;
    for (int j = len - 1; ~j; --j) {
      long long sum = 0;
      for (int k = last; k < 16; ++k) {
        if (state < sum + dp[j][k]) {
          send(i * 4 + k);
          state -= sum;
          last = k;
          break;
        }
        sum += dp[j][k];
      }
    }
  }
}

decoder

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

using namespace std;

void decode(int N, int L, int X[]) {
  vector<vector<long long>> dp(21, vector<long long>(16));
  for (int i = 0; i < 16; ++i) {
    dp[0][i] = 1;
  }
  for (int i = 1; i < 21; ++i) {
    for (int j = 0; j < 16; ++j) {
      for (int k = j; k < 16; ++k) {
        dp[i][j] += dp[i - 1][k];
      }
    }
  }
  vector<long long> sum(21);
  for (int i = 1; i < 21; ++i) {
    sum[i] = sum[i - 1] + dp[i][0];
  }
  int n = N;
  while (N % 4) {
    ++N;
  }
  for (int i = 0; i < N; i += 4) {
    long long state = 0;
    vector<int> sorted;
    for (int j = 0; j < L; ++j) {
      if (X[j] / 16 == i / 4) {
        sorted.push_back(X[j] % 16);
      }
    }
    sort(sorted.begin(), sorted.end());
    int len = (int) sorted.size();
    int last = 0;
    for (int j = len - 1; ~j; --j) {
      for (int k = last; k < sorted[len - 1 - j]; ++k) {
        state += dp[j][k];
      }
      last = sorted[len - 1 - j];
    }
    state += sum[len - 1];
    for (int j = 0; j < 4; ++j) {
      if (i + j < n) {
        output((state >> (j * 8)) & 255);
      }
    }
  }
}

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