oj.uz

Submission #752770

# Submission time Handle Problem Language Result Execution time Memory
752770 2023-06-03T20:18:55 Z nicksms Parrots (IOI11_parrots) C++17
100 / 100
 7 ms 1872 KB 
#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));
  }
}

#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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1168 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1548 KB Output is correct
2 Correct 2 ms 1548 KB Output is correct
3 Correct 4 ms 1564 KB Output is correct
4 Correct 3 ms 1564 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1556 KB Output is correct
2 Correct 2 ms 1556 KB Output is correct
3 Correct 4 ms 1560 KB Output is correct
4 Correct 3 ms 1528 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1544 KB Output is correct
2 Correct 3 ms 1564 KB Output is correct
3 Correct 3 ms 1504 KB Output is correct
4 Correct 3 ms 1568 KB Output is correct
5 Correct 6 ms 1692 KB Output is correct
6 Correct 3 ms 1572 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1564 KB Output is correct - P = 4.625000
2 Correct 4 ms 1572 KB Output is correct - P = 4.625000
3 Correct 3 ms 1572 KB Output is correct - P = 4.545455
4 Correct 6 ms 1728 KB Output is correct - P = 4.540000
5 Correct 6 ms 1860 KB Output is correct - P = 4.516667
6 Correct 7 ms 1840 KB Output is correct - P = 4.571429
7 Correct 7 ms 1872 KB Output is correct - P = 4.625000