Submission #990655

#	Time	Username	Problem	Language	Result	Execution time	Memory
990655		AdamGS	Parrots (IOI11_parrots)	C++17	100 / 100	5 ms	1356 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
__int128_t dpp[33][41];
vector<ll>koduj(__int128_t x) {
  ll dlu=0;
  while(dpp[32][dlu]<=x) {
    x-=dpp[32][dlu];
    ++dlu;
  }
  vector<ll>ans(32);
  ll c=32;
  while(dlu>0 && c>0) {
    if(c==1) {
      ++ans[0];
      --dlu;
      continue;
    }
    if(dpp[c-1][dlu]<=x) {
      x-=dpp[c-1][dlu];
      ++ans[c-1];
      --dlu;
    } else --c;
  }
  return ans;
}
void encode(int n, int _T[]) {
  dpp[1][0]=1;
  for(int x=1; x<=32; ++x) {
    for(int y=1; y<=40; ++y) dpp[x][y]=dpp[x-1][y]+dpp[x][y-1];
  }
  vector<ll>T(n);
  rep(i, n) T[i]=_T[i];
  while(T.size()%8!=0) T.pb(0);
  if(n%2==1) T.pb(0);
  rep(i, (n+7)/8) {
    __int128_t x=0;
    rep(j, 8) x=x*256+T[8*i+7-j];
    vector<ll>P=koduj(x);
    rep(j, 32) rep(l, P[j]) send(32*i+j);
  }
}

decoder

#include "decoder.h"
#include "decoderlib.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
__int128_t dp[33][41];
__int128_t odkoduj(vector<ll>T) {
  __int128_t x=0, sum=0;
  rep(i, 32) sum+=T[i];
  rep(i, sum) x+=dp[32][i];
  rep(i, 31) {
    rep(j, T[31-i]) {
      x+=dp[31-i][sum];
      --sum;
    }
  }
  return x;
}
void decode(int n, int l, int _T[]) {
  dp[0][1]=1;
  for(int x=1; x<=32; ++x) {
    for(int y=1; y<=40; ++y) dp[x][y]=dp[x-1][y]+dp[x][y-1];
  }
  vector<ll>T(256);
  rep(i, l) ++T[_T[i]];
  vector<ll>ans(n+7);
  rep(i, (n+7)/8) {
    vector<ll>P(32);
    rep(j, 32) P[j]=T[32*i+j];
    __int128_t x=odkoduj(P);
    rep(j, 8) {
      ans[8*i+j]=x%256;
      x/=256;
    }
  }
  rep(i, n) output(ans[i]);
}

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