#include "encoder.h"
#include "encoderlib.h"
#include <bitset>
#include <cassert>
#include <iostream>
#include <array>
using namespace std;
const int LEN = 514, LIM = 517;
static bitset<LEN> operator+ (const bitset<LEN> &lhs, const bitset<LEN> &rhs) {
bitset<LEN> res;
res.reset();
bool carry = 0;
for (int i = 0; i < LEN; i++) {
res[i] = carry ^ lhs[i] ^ rhs[i];
if ((carry && lhs[i]) || (carry && rhs[i]) || (lhs[i] && rhs[i])) {
carry = 1;
} else {
carry = 0;
}
}
assert(carry == 0);
return res;
}
static bool fullSubtractor(bool b1, bool b2, bool& borrow) {
bool diff;
if (borrow) {
diff = !(b1 ^ b2);
borrow = !b1 || (b1 && b2);
}
else {
diff = b1 ^ b2;
borrow = !b1 && b2;
}
return diff;
}
static bitset<LEN> operator- (const bitset<LEN> &lhs, const bitset<LEN> &rhs) {
bool borrow = 0;
bitset<LEN> ans;
for (int i = 0; i < LEN; i++) {
ans[i] = fullSubtractor(lhs[i], rhs[i], borrow);
}
return ans;
}
bool lessThanOrEqualTo(const bitset<LEN> &lhs, const bitset<LEN> &rhs) {
auto tmp = lhs ^ rhs;
int pos = -1;
for (int i = LEN - 1; i >= 0; i--) {
if (tmp[i]) {
pos = i;
break;
}
}
if (lhs[pos]) return 0;
else return 1;
}
static bitset<LEN> nck[LIM][LIM];
static void precompute_binomials() {
for (int i = 0; i < LIM; i++) {
for (int j = 0; j <= i; j++) {
if (i == 0 || j == 0) {
nck[i][j] = j == 0;
} else {
nck[i][j] = nck[i - 1][j] + nck[i - 1][j - 1];
}
}
}
}
static bool init;
void encode(int N, int M[]) {
int K = min(261, N * 5);
if (!init) {
precompute_binomials();
init = 1;
}
bitset<LEN> cur;
cur.reset();
for (int i = 0; i < N; i++) {
for (int j = 0; j < 8; j++) {
cur[i * 8 + j] = !!(M[i] & (1 << j));
}
}
for (int i = 0, val = 0; i < K; i++) {
while (1) {
int len_left = K - 1 - i;
int vals_left = 256 - val;
if (lessThanOrEqualTo(nck[len_left + vals_left][vals_left], cur)) {
cur = cur - nck[len_left + vals_left][vals_left];
val++;
} else {
break;
}
}
send(val);
}
}
#include "decoder.h"
#include "decoderlib.h"
#include <bitset>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <array>
using namespace std;
int A[105];
const int LEN = 514, LIM = 517;
static bitset<LEN> operator+ (const bitset<LEN> &lhs, const bitset<LEN> &rhs) {
bitset<LEN> res;
res.reset();
bool carry = 0;
for (int i = 0; i < LEN; i++) {
res[i] = carry ^ lhs[i] ^ rhs[i];
if ((carry && lhs[i]) || (carry && rhs[i]) || (lhs[i] && rhs[i])) {
carry = 1;
} else {
carry = 0;
}
}
assert(carry == 0);
return res;
}
static bool fullSubtractor(bool b1, bool b2, bool& borrow) {
bool diff;
if (borrow) {
diff = !(b1 ^ b2);
borrow = !b1 || (b1 && b2);
}
else {
diff = b1 ^ b2;
borrow = !b1 && b2;
}
return diff;
}
static bitset<LEN> operator- (const bitset<LEN> &lhs, const bitset<LEN> &rhs) {
bool borrow = 0;
bitset<LEN> ans;
for (int i = 0; i < LEN; i++) {
ans[i] = fullSubtractor(lhs[i], rhs[i], borrow);
}
return ans;
}
static bitset<LEN> nck[LIM][LIM];
static void precompute_binomials() {
for (int i = 0; i < LIM; i++) {
for (int j = 0; j <= i; j++) {
if (i == 0 || j == 0) {
nck[i][j] = j == 0;
} else {
nck[i][j] = nck[i - 1][j] + nck[i - 1][j - 1];
}
}
}
}
static bool init;
void decode(int N, int L, int X[]) {
int K = min(261, N * 5);
if (!init) {
precompute_binomials();
init = 1;
}
sort(X, X + L);
bitset<LEN> num(0);
for (int i = 0; i < L; i++) {
int len_left = L - i - 1;
for (int val = i ? X[i - 1] : 0; val < X[i]; val++) {
int val_left = 256 - val;
num = num + nck[len_left + val_left][val_left];
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < 8; j++) {
if (num[i * 8 + j]) {
A[i] |= (1 << j);
}
}
output(A[i]);
}
}
Compilation message
decoder.cpp: In function 'void decode(int, int, int*)':
decoder.cpp:69:6: warning: unused variable 'K' [-Wunused-variable]
69 | int K = min(261, N * 5);
| ^
decoder.cpp: At global scope:
decoder.cpp:43:20: warning: 'std::bitset<514> operator-(const std::bitset<514>&, const std::bitset<514>&)' defined but not used [-Wunused-function]
43 | static bitset<LEN> operator- (const bitset<LEN> &lhs, const bitset<LEN> &rhs) {
| ^~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
247 ms |
23496 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
248 ms |
23628 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
247 ms |
23488 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
247 ms |
23556 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
244 ms |
23500 KB |
Execution killed with signal 11 |
2 |
Runtime error |
241 ms |
23500 KB |
Execution killed with signal 11 |
3 |
Runtime error |
243 ms |
23488 KB |
Execution killed with signal 11 |
4 |
Runtime error |
249 ms |
23680 KB |
Execution killed with signal 11 |
5 |
Runtime error |
247 ms |
23572 KB |
Execution killed with signal 11 |
6 |
Runtime error |
253 ms |
23472 KB |
Execution killed with signal 11 |
7 |
Runtime error |
246 ms |
23560 KB |
Execution killed with signal 11 |