제출 #118298

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
118298		MAMBA	앵무새 (IOI11_parrots)	C++17	0 / 100	11 ms	1432 KiB

encoder

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

using namespace std;

inline void read() {}
template <class S>
inline void read(S &arg) {
  cin >> arg;
}
template <class S>
inline void readA(S Lptr, S Rptr) {
  while (Lptr != Rptr) {
    read(*Lptr);
    Lptr++;
  }
}
template <class S, class... T>
inline void read(S &arg, T &... rest) {
  read(arg);
  read(rest...);
}

inline void write() {}
template <class S>
inline void write(S arg) {
  cout << arg;
}
template <class S>
inline void writeA(S Lptr, S Rptr, char C_ = ' ') {
  if (Lptr != Rptr) {
    write(*Lptr);
    Lptr++;
  }
  while (Lptr != Rptr) {
    write(C_);
    write(*Lptr);
    Lptr++;
  }
}
template <class S, class... T>
inline void write(S arg, T... rest) {
  write(arg);
  write(' ');
  write(rest...);
}

#define rep(i, j, k) for (int i = j; i < (int)k; i++)
#define pb push_back
#define mt make_tuple
#define all(x) x.begin(), x.end()

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

template <class T, class S>
inline bool smin(T &a, S b) {
  return (T)b < a ? a = b, 1 : 0;
}
template <class T, class S>
inline bool smax(T &a, S b) {
  return a < (T)b ? a = b, 1 : 0;
}

constexpr int MOD = 1e9 + 7;
constexpr int N = 150 * 1000 + 10;

template <typename T>
inline T mod(T &v) {
  return v = (v % MOD + MOD) % MOD;
}
template <typename S, typename T>
inline S add(S &l, T r) {
  return mod(l += r);
}

ll po(ll v, ll u) {
  return u ? po(v * v % MOD, u >> 1) * (u & 1 ? v : 1) % MOD : 1;
}

typedef bitset<2048> sagy;

sagy operator+(sagy l, sagy r) {
  sagy res;
  bool cary = false;
  rep(i, 0, 2048) {
    int me = (cary ? 1 : 0) + (l[i] ? 1 : 0) + (r[i] ? 1 : 0);
    if (me & 1) res[i] = true;
    if (me > 1) cary = true;
  }
  assert(!cary);
  return res;
}

bool operator<(sagy l, sagy r) {
  l ^= r;
  int id = -1;
  rep(i, 0, 2048) if (l[i]) id = i;
  return r[id];
}

const int L = 257;
const int R = L + 64 * 5;
sagy c[L][R];

inline void init() {
  rep(i, 0, R) {
    c[0][i][0] = true;
    c[i][i][0] = true;
    rep(j, 1, min(i , L)) c[j][i] = c[j - 1][i - 1] + c[j][i - 1];
  }
}

int cnt[L];

void encode(int N, int M[]) {
  return;
  init();
  sagy code;
  rep(i, 0, N) rep(j, 0, 8) code[(i << 3) + j] = (M[i] >> j) & 1;
  sagy ta_hala;
  int have = 5 * N;
  for (int i = 255; ~i; i--) {
    while (true) {
      sagy ta_alan = ta_hala;
      have--;
      cnt[i]++;
      ta_alan = ta_alan + c[i][have + i];
      if (code < ta_alan) {
        have++;
        cnt[i]--;
        break;
      }
      ta_hala = ta_alan;
    }
  }
  rep(i, 0, 256) rep(j, 0, cnt[i]) send(i);
}

decoder

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

using namespace std;

inline void read() {}
template <class S>
inline void read(S &arg) {
  cin >> arg;
}
template <class S>
inline void readA(S Lptr, S Rptr) {
  while (Lptr != Rptr) {
    read(*Lptr);
    Lptr++;
  }
}
template <class S, class... T>
inline void read(S &arg, T &... rest) {
  read(arg);
  read(rest...);
}

inline void write() {}
template <class S>
inline void write(S arg) {
  cout << arg;
}
template <class S>
inline void writeA(S Lptr, S Rptr, char C_ = ' ') {
  if (Lptr != Rptr) {
    write(*Lptr);
    Lptr++;
  }
  while (Lptr != Rptr) {
    write(C_);
    write(*Lptr);
    Lptr++;
  }
}
template <class S, class... T>
inline void write(S arg, T... rest) {
  write(arg);
  write(' ');
  write(rest...);
}

#define rep(i, j, k) for (int i = j; i < (int)k; i++)
#define pb push_back
#define mt make_tuple
#define all(x) x.begin(), x.end()

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

template <class T, class S>
inline bool smin(T &a, S b) {
  return (T)b < a ? a = b, 1 : 0;
}
template <class T, class S>
inline bool smax(T &a, S b) {
  return a < (T)b ? a = b, 1 : 0;
}

constexpr int MOD = 1e9 + 7;
constexpr int N = 150 * 1000 + 10;

template <typename T>
inline T mod(T &v) {
  return v = (v % MOD + MOD) % MOD;
}
template <typename S, typename T>
inline S add(S &l, T r) {
  return mod(l += r);
}

ll po(ll v, ll u) {
  return u ? po(v * v % MOD, u >> 1) * (u & 1 ? v : 1) % MOD : 1;
}

typedef bitset<2048> sagy;

sagy operator+(sagy l, sagy r) {
  sagy res;
  bool cary = false;
  rep(i, 0, 2048) {
    int me = (cary ? 1 : 0) + (l[i] ? 1 : 0) + (r[i] ? 1 : 0);
    if (me & 1) res[i] = true;
    if (me > 1) cary = true;
  }
  assert(!cary);
  return res;
}

bool operator<(sagy l, sagy r) {
  l ^= r;
  int id = -1;
  rep(i, 0, 2048) if (l[i]) id = i;
  return r[id];
}

const int L = 257;
const int R = L + 64 * 5;
sagy c[L][R];

inline void init() {
  rep(i, 0, R) {
    c[0][i][0] = true;
    c[i][i][0] = true;
    rep(j, 1, min(i, L)) c[j][i] = c[j - 1][i - 1] + c[j][i - 1];
  }
}

int cnt[L];

void decode(int N, int L, int X[]) {
  return;
  init();
  rep(i, 0, L) cnt[X[i]]++;
  sagy code;
  int have = 5 * N;
  for (int i = 255; ~i; i--) {
    while (cnt[i] > 1) {
      code = code + c[i][have + i];
      have--;
      cnt[i]--;
    }
    have--;
  }
  code = code + c[0][0];
  rep(i, 0, N) {
    int res = 0;
    rep(j, 0, 8) if (code[(i << 3) + j]) res += (1 << j);
    output(res);
  }
}

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