| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 118309 | MAMBA | Parrots (IOI11_parrots) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "encoder.h"
#include <bits/stdc++.h>
#include "encoderlib.h"
using namespace std;
#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 N = 150 * 1000 + 10;
const int LEN = (1 << 9);
typedef int[LEN] sagy;
sagy operator+(sagy l, sagy r) {
sagy res;
bool cary = false;
rep(i, 0, LEN) {
ll tmp = 1ll * l[i] + r[i] + (cary ? 1: 0);
res[i] = tmp & ((1l << 32) - 1);
cary = tmp >> 32;
}
assert(!cary);
return res;
}
bool operator<(sagy l, sagy r) {
for (int i = LEN - 1; ~i; i--) {
int tmp = l[i] ^ r[i];
if (tmp) {
for (int j = 31; ; j--) {
if ((tmp >> j) & 1)
return (r >> j) & 1;
}
}
}
return false;
}
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;
if (i < L) 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[]) {
init();
return;
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);
}
#include "decoder.h"
#include <bits/stdc++.h>
#include "decoderlib.h"
using namespace std;
#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 N = 150 * 1000 + 10;
const int LEN = (1 << 9);
typedef int[LEN] sagy;
sagy operator+(sagy l, sagy r) {
sagy res;
bool cary = false;
rep(i, 0, LEN) {
ll tmp = 1ll * l[i] + r[i] + (cary ? 1: 0);
res[i] = tmp & ((1l << 32) - 1);
cary = tmp >> 32;
}
assert(!cary);
return res;
}
bool operator<(sagy l, sagy r) {
for (int i = LEN - 1; ~i; i--) {
int tmp = l[i] ^ r[i];
if (tmp) {
for (int j = 31; ; j--) {
if ((tmp >> j) & 1)
return (r >> j) & 1;
}
}
}
return false;
}
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;
if (i < L) 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);
}
}