이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//START COPY
#include <bits/stdc++.h>
#include "encoderlib.h"
using namespace std;
typedef long long ll;
#define fillchar(a, s) memset((a), (s), sizeof(a))
struct bigint1 {
unsigned arr[18];
bigint1() {
fillchar(arr, 0);
}
bigint1 (int x) {
fillchar(arr, 0);
arr[0] = x;
}
};
static void operator += (bigint1 &b1, bigint1 b2) {
bool carry = 0;
for (int i = 0; i < 18; i++) {
ll x = ll(b1.arr[i]) + b2.arr[i] + carry;
b1.arr[i] = x;
carry = (x >= (1ll << 32));
}
}
static void operator -= (bigint1 &b1, bigint1 b2) {
//b1 + (~b2) + 1
//optimize the +1
for (int i = 0; i < 18; i++) {
b2.arr[i] = ~b2.arr[i];
}
b1 += b2;
b1 += bigint1(1);
}
static bigint1 operator + (bigint1 b1, bigint1 b2) {
b1 += b2;
return b1;
}
static bigint1 operator - (bigint1 b1, bigint1 b2) {
b1 -= b2;
return b1;
}
static bool operator < (bigint1 b1, bigint1 b2) {
for (int i = 17; i >= 0; i--) {
if (b1.arr[i] < b2.arr[i]) {
return true;
}
if (b1.arr[i] > b2.arr[i]) {
return false;
}
}
return false;
}
static bool operator >= (bigint1 b1, bigint1 b2) {
return !(b1 < b2);
}
static bool operator > (bigint1 b1, bigint1 b2) {
return b2 < b1;
}
static bool operator <= (bigint1 b1, bigint1 b2) {
return !(b2 < b1);
}
static const int MAXV = 5 * 32 + 256;
static bigint1 cho[MAXV][256];
static void precomp() {
for (int i = 0; i < MAXV; i++) {
cho[i][0].arr[0] = 1;
for (int j = 1; j <= i && j < 256; j++) {
cho[i][j] = cho[i - 1][j] + cho[i - 1][j - 1];
}
}
}
static bigint1 nsum (int n, int s) {
return cho[n + s - 1][n - 1];
}
static int N;
static int K;
//END COPY
void encode (int nn, int mm[]) {
N = nn;
K = 5 * N;
precomp();
//ok let's go!
bigint1 rnk = bigint1();
for (int i = 0; i < N; i++) {
rnk.arr[i / 4] |= (mm[i] << (8 * (i % 4)));
}
//ok now get this number rank
vector<int> ans;
for (int i = 0; i < K; i++) {
//if you put this one then what will you get?
int prv = (ans.empty() ? 0 : ans.back());
for (int j = prv; j < 256; j++) {
//test if next one is > j.
//if not then choose this one and break
bigint1 nways = nsum(256 - j, K - 1 - i);
if (rnk >= nways) {
rnk -= nways;
} else {
ans.push_back(j);
break;
}
}
}
//printf("SEND:");
for (int x : ans) {
//printf(" %d", x);
send(x);
}
//printf("\n");
}
//START COPY
#include <bits/stdc++.h>
#include "decoderlib.h"
using namespace std;
typedef long long ll;
#define fillchar(a, s) memset((a), (s), sizeof(a))
struct bigint2 {
unsigned arr[18];
bigint2() {
fillchar(arr, 0);
}
bigint2 (int x) {
fillchar(arr, 0);
arr[0] = x;
}
};
static void operator += (bigint2 &b1, bigint2 b2) {
bool carry = 0;
for (int i = 0; i < 18; i++) {
ll x = ll(b1.arr[i]) + b2.arr[i] + carry;
b1.arr[i] = x;
carry = (x >= (1ll << 32));
}
}
static void operator -= (bigint2 &b1, bigint2 b2) {
//b1 + (~b2) + 1
//optimize the +1
for (int i = 0; i < 18; i++) {
b2.arr[i] = ~b2.arr[i];
}
b1 += b2;
b1 += bigint2(1);
}
static bigint2 operator + (bigint2 b1, bigint2 b2) {
b1 += b2;
return b1;
}
static bigint2 operator - (bigint2 b1, bigint2 b2) {
b1 -= b2;
return b1;
}
static bool operator < (bigint2 b1, bigint2 b2) {
for (int i = 17; i >= 0; i--) {
if (b1.arr[i] < b2.arr[i]) {
return true;
}
if (b1.arr[i] > b2.arr[i]) {
return false;
}
}
return false;
}
static bool operator >= (bigint2 b1, bigint2 b2) {
return !(b1 < b2);
}
static bool operator > (bigint2 b1, bigint2 b2) {
return b2 < b1;
}
static bool operator <= (bigint2 b1, bigint2 b2) {
return !(b2 < b1);
}
static const int MAXV = 5 * 32 + 256;
static bigint2 cho[MAXV][256];
static void precomp() {
for (int i = 0; i < MAXV; i++) {
cho[i][0].arr[0] = 1;
for (int j = 1; j <= i && j < 256; j++) {
cho[i][j] = cho[i - 1][j] + cho[i - 1][j - 1];
}
}
}
static bigint2 nsum (int n, int s) {
return cho[n + s - 1][n - 1];
}
static int N;
static int K;
//END COPY
void decode (int nn, int kk, int X[]) {
N = nn;
K = kk;
precomp();
//find the rank of this one
bigint2 rnk = bigint2();
for (int i = 0; i < K; i++) {
int prv = (i == 0 ? 0 : X[i - 1]);
for (int j = prv; j < X[i]; j++) {
//add this amount of stuff
bigint2 nways = nsum(256 - j, K - 1 - i);
rnk += nways;
}
}
//printf("OUTPUT:");
for (int i = 0; i < N; i++) {
//ok let's do this
int val = (rnk.arr[i / 4] >> (8 * (i % 4))) & 255;
//printf(" %d", val);
output(val);
}
//printf("\n");
}
컴파일 시 표준 에러 (stderr) 메시지
encoder.cpp:72:13: warning: 'bool operator<=(bigint1, bigint1)' defined but not used [-Wunused-function]
static bool operator <= (bigint1 b1, bigint1 b2) {
^~~~~~~~
encoder.cpp:68:13: warning: 'bool operator>(bigint1, bigint1)' defined but not used [-Wunused-function]
static bool operator > (bigint1 b1, bigint1 b2) {
^~~~~~~~
encoder.cpp:47:16: warning: 'bigint1 operator-(bigint1, bigint1)' defined but not used [-Wunused-function]
static bigint1 operator - (bigint1 b1, bigint1 b2) {
^~~~~~~~
decoder.cpp:72:13: warning: 'bool operator<=(bigint2, bigint2)' defined but not used [-Wunused-function]
static bool operator <= (bigint2 b1, bigint2 b2) {
^~~~~~~~
decoder.cpp:68:13: warning: 'bool operator>(bigint2, bigint2)' defined but not used [-Wunused-function]
static bool operator > (bigint2 b1, bigint2 b2) {
^~~~~~~~
decoder.cpp:64:13: warning: 'bool operator>=(bigint2, bigint2)' defined but not used [-Wunused-function]
static bool operator >= (bigint2 b1, bigint2 b2) {
^~~~~~~~
decoder.cpp:47:16: warning: 'bigint2 operator-(bigint2, bigint2)' defined but not used [-Wunused-function]
static bigint2 operator - (bigint2 b1, bigint2 b2) {
^~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |