Submission #1219468

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

encoder

#include "encoder.h"
#include "encoderlib.h"
#include<bits/stdc++.h>
using namespace std;

#define ll long long

ll dp[36][36];

void filldp(){
  dp[0][0] = 1;
  for (int i=1; i<=35; i++){
    dp[i][0] = 1;
    dp[i][i] = 1;
    for (int j=1; j<i; j++) dp[i][j] = dp[i-1][j]+dp[i-1][j-1];
  }
}

vector<int> numtoseq(ll x){
  int siz = 0;
  while (x >= dp[siz+15][15]){
    x -= dp[siz+15][15];
    siz++;
  }
  vector<int> seq(siz, 0);
  for (int i=0; i<siz; i++){
    while (x >= dp[siz-i-1+seq[i]][seq[i]]){
      x -= dp[siz-i-1+seq[i]][seq[i]];
      seq[i]++;
    }
  }
  return seq;
}

void encode(int N, int M[]){
  filldp();
  for (int chunk=0; chunk<N; chunk+=4){
    ll x = 0;
    for (int i=chunk; i<min(N, chunk+4); i++) x += (ll)M[i]*(ll)pow(256, i-chunk);
    vector<int> seq = numtoseq(x);
    for (int y : seq){
      send(chunk*4+y);
    }
  }
}

decoder

#include "decoder.h"
#include "decoderlib.h"
#include<bits/stdc++.h>
using namespace std;

#define ll long long

ll dp2[36][36];

void filldp2(){
  dp2[0][0] = 1;
  for (int i=1; i<=35; i++){
    dp2[i][0] = 1;
    dp2[i][i] = 1;
    for (int j=1; j<i; j++) dp2[i][j] = dp2[i-1][j]+dp2[i-1][j-1];
  }
}

ll seqtonum(vector<int> seq){
  ll x = 0;
  for (int i=0; i<(int)seq.size(); i++){
    x += dp2[i+15][15];
  }
  for (int i=0; i<(int)seq.size(); i++){
    for (int j=0; j<seq[i]; j++){
      x += dp2[seq.size()-i-1+j][j];
    }
  }
  return x;
}

void decode(int N, int L, int X[]){
  filldp2();
  sort(X, X+L);
  int cur = 0;
  for (int chunk=0; chunk<N; chunk+=4){
    vector<int> seq;
    while (cur < L && (X[cur]/16)*4 == chunk){
      seq.push_back(X[cur] % 16);
      cur++;
    }
    reverse(seq.begin(), seq.end());
    ll x = seqtonum(seq);
    for (int i=chunk; i<min(N, chunk+4); i++){
      output(x % 256);
      x /= 256;
    }
  }
}

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