Submission #752770

#	Time	Username	Problem	Language	Result	Execution time	Memory
752770		nicksms	Parrots (IOI11_parrots)	C++17	100 / 100	7 ms	1872 KiB

encoder

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


/**
 *      Author:  Nicholas Winschel
 *      Created: 06.03.2023 15:16:06
**/

#include <bits/stdc++.h>
using namespace std;
using lll=__uint128_t;
using ll=unsigned long long;
using db=long double;
template<class T> using V=vector<T>;
using vi = V<int>;
using vl = V<ll>;
using pi = pair<int,int>;
#define f first
#define s second
#define sz(x) (int)((x).size())

namespace encodesms {
const int MAXN=128;

lll C[MAXN][MAXN];

bool initd=false;
void init() {
  if (initd) return;
  initd=true;
  for (int i = 0; i < MAXN; i++) {
    C[i][0]=C[i][i]=1;
    if (i) for (int j = 1; j < i; j++) {
      C[i][j] = C[i-1][j-1] + C[i-1][j];
    }
  }
}

ll decblk(vi sord) {
  init();
  int n = sz(sord);
  lll curg = 0;
  for (int i = 0; i < n; i++) {
    if (sord[i]==31) break;
    curg += C[30-sord[i] + n - i][n-i]; 
  }
  assert(curg < ((lll(1))<<64));
  return (ll)curg;
}

vi encblk(ll inp) {
  init();
  lll k = (lll)inp;
  int len = 0;
  while (C[len+31][len]<=inp) len++;
  vi ret(len, 31);
  for (int i = 0; i < len; i++) {
    while (((i == 0 && ret[i] > 0) || ret[i] > ret[i-1]) && k >= (C[30-(ret[i]-1) + len-i][len-i])) ret[i]--;
    if (ret[i] != 31) k -= C[30-(ret[i])+len-i][len-i];
  }
  assert(k == 0);
  return ret;
}
}
using namespace encodesms;

void encode(int N, int M[])
{
  vl blks(8);
  for (int i = 0; i < N; i++) {
    ll c = M[i];
    blks[i/8] |= (c<<(8*(i&7)));
  }
  // cerr << "enc: \n";
  // cerr << "blks: ";
  // for (auto p : blks) cout << p << " ";
  // cout << "\n";
  for (int i = 0; i < 8; i++) {
    vi enc = encblk(blks[i]);
    for (int x : enc) send(x | (i<<5));
  }
}

decoder

#include "decoder.h"
#include "decoderlib.h"
/**
 *      Author:  Nicholas Winschel
 *      Created: 06.03.2023 15:16:06
**/

#include <bits/stdc++.h>
using namespace std;
using lll=__uint128_t;
using ll=unsigned long long;
using db=long double;
template<class T> using V=vector<T>;
using vi = V<int>;
using vl = V<ll>;
using pi = pair<int,int>;
#define f first
#define s second
#define sz(x) (int)((x).size())
namespace decodesms {
const int MAXN=128;

lll C[MAXN][MAXN];

bool initd=false;
void init() {
  if (initd) return;
  initd=true;
  for (int i = 0; i < MAXN; i++) {
    C[i][0]=C[i][i]=1;
    if (i) for (int j = 1; j < i; j++) {
      C[i][j] = C[i-1][j-1] + C[i-1][j];
    }
  }
}

ll decblk(vi sord) {
  init();
  int n = sz(sord);
  lll curg = 0;
  for (int i = 0; i < n; i++) {
    if (sord[i]==31) break;
    curg += C[30-sord[i] + n - i][n-i]; 
  }
  assert(curg < ((lll(1))<<64));
  return (ll)curg;
}

vi encblk(ll inp) {
  init();
  lll k = (lll)inp;
  int len = 0;
  while (C[len+31][len]<=inp) len++;
  vi ret(len, 31);
  for (int i = 0; i < len; i++) {
    while (((i == 0 && ret[i] > 0) || ret[i] > ret[i-1]) && k >= (C[30-(ret[i]-1) + len-i][len-i])) ret[i]--;
    if (ret[i] != 31) k -= C[30-(ret[i])+len-i][len-i];
  }
  assert(k == 0);
  return ret;
}
}
using namespace decodesms;
// int main() {
//   ll k = (1<<16)-1;
//   cout << k << "\n";
//   vi test = encblk(k);
//   for (auto p : test) cout << p << " ";
//   cout << "\n";
//   cout << decblk(test);
//   assert(decblk(test)==(k));
// }

void decode(int N, int L, int X[]) {
  sort(X,X+L);
  vl ans(8);
  V<vi> sord(8);
  for (int i = 0; i < L; i++) {
    int ind = X[i]>>5;
    sord[ind].push_back(X[i]&((1<<5)-1));
  }
  for (int i = 0; i < 8; i++) ans[i]=decblk(sord[i]);
  const int m = (1<<8)-1;
  for (int i = 0; i < N; i++) {
    output(m & (ans[i/8] >> (8*(i&7))));
  }
}

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