| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 676784 | Alan | 앵무새 (IOI11_parrots) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct BigInt {
static const ll unit = 1000000000, digit = 9;
vector<ll> x {0};
BigInt () {}
BigInt (vector<ll> y) {
x = y;
}
BigInt (ll y) {
x.resize(3);
x[0] = y%unit;
x[1] = y/unit%unit;
x[2] = y/unit/unit;
while (x.back() == 0 && (int) x.size() > 1) x.pop_back();
}
BigInt operator+ (BigInt y) {
BigInt tmp = BigInt(x);
if (y.x.size() < tmp.x.size()) swap(y, tmp);
for (int i = 0; i < (int) tmp.x.size(); i++) y.x[i] += tmp.x[i];
y.x.push_back(0);
for (int i = 0; i < (int) y.x.size()-1; i++) if (y.x[i] >= 1e9) {
y.x[i+1] += y.x[i]/unit;
y.x[i] %= unit;
}
if ((int) y.x.size() > 1 && y.x.back() == 0) y.x.pop_back();
return y;
}
BigInt operator* (BigInt y) {
BigInt tmp = BigInt(x), res (0);
res.x.resize(y.x.size()+tmp.x.size()+1);
for (int i = 0; i < (int) y.x.size(); i++) for (int j = 0; j < (int) tmp.x.size(); j++) res.x[i+j] += y.x[i]*tmp.x[j];
for (int i = 0; i < (int) res.x.size()-1; i++) if (res.x[i] >= 1e9) {
res.x[i+1] += res.x[i]/unit;
res.x[i] %= unit;
}
while ((int) res.x.size() > 1 && res.x.back() == 0) res.x.pop_back();
return res;
}
bool operator== (BigInt y) {
if (x.size() != y.x.size()) return false;
for (int i = 0; i < (int) x.size(); i++) if (x[i] != y.x[i]) return false;
return true;
}
bool operator<= (BigInt y) {
if (x.size() < y.x.size()) return true;
if (x.size() > y.x.size()) return false;
for (int i = (int) x.size()-1; i >= 0; i--) {
if (x[i] < y.x[i]) return true;
if (x[i] > y.x[i]) return false;
}
return true;
}
};
BigInt pow (BigInt x, ll p) {
if (!p) return BigInt(1);
BigInt t = pow(x, p/2);
t = t*t;
return p % 2 == 1 ? t * x : t;
}
BigInt ncr[600][350];
void precomp () {
for (int i = 0; i < 600; i++) for (int j = 0; j <= min(i, 400); j++) {
if (j == 0 || j == i) ncr[i][j] = BigInt(1);
else ncr[i][j] = ncr[i-1][j]+ncr[i-1][j-1];
}
}
void encode (int n, int m[]) {
precomp();
BigInt res (0), rep (0);
for (int i = 0; i < n; i++) res = res + BigInt(m[i]) * pow(BigInt(256), i);
int last = 0;
for (int i = 0; i < n*5; i++) {
if (i == n*5-1) {
for (int j = 0; j < 256; j++) if (rep+BigInt(j) == res) {
send(last+j);
break;
}
break;
}
while (rep + ncr[254-last+n*5-i][n*5-i-1] <= res) {
rep = rep + ncr[254-last+n*5-i][n*5-i-1];
last++;
}
send(last);
}
}
#include "decoder.h"
#include "decoderlib.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct BigInt {
static const ll unit = 1000000000, digit = 9;
vector<ll> x {0};
BigInt () {}
BigInt (vector<ll> y) {
x = y;
}
BigInt (ll y) {
x.resize(3);
x[0] = y%unit;
x[1] = y/unit%unit;
x[2] = y/unit/unit;
while (x.back() == 0 && (int) x.size() > 1) x.pop_back();
}
BigInt operator+ (BigInt y) {
BigInt tmp = BigInt(x);
if (y.x.size() < tmp.x.size()) swap(y, tmp);
for (int i = 0; i < (int) tmp.x.size(); i++) y.x[i] += tmp.x[i];
y.x.push_back(0);
for (int i = 0; i < (int) y.x.size()-1; i++) if (y.x[i] >= 1e9) {
y.x[i+1] += y.x[i]/unit;
y.x[i] %= unit;
}
if ((int) y.x.size() > 1 && y.x.back() == 0) y.x.pop_back();
return y;
}
BigInt operator* (BigInt y) {
BigInt tmp = BigInt(x), res (0);
res.x.resize(y.x.size()+tmp.x.size()+1);
for (int i = 0; i < (int) y.x.size(); i++) for (int j = 0; j < (int) tmp.x.size(); j++) res.x[i+j] += y.x[i]*tmp.x[j];
for (int i = 0; i < (int) res.x.size()-1; i++) if (res.x[i] >= 1e9) {
res.x[i+1] += res.x[i]/unit;
res.x[i] %= unit;
}
while ((int) res.x.size() > 1 && res.x.back() == 0) res.x.pop_back();
return res;
}
bool operator== (BigInt y) {
if (x.size() != y.x.size()) return false;
for (int i = 0; i < (int) x.size(); i++) if (x[i] != y.x[i]) return false;
return true;
}
bool operator<= (BigInt y) {
if (x.size() < y.x.size()) return true;
if (x.size() > y.x.size()) return false;
for (int i = (int) x.size()-1; i >= 0; i--) {
if (x[i] < y.x[i]) return true;
if (x[i] > y.x[i]) return false;
}
return true;
}
};
extern BigInt ncr[600][350];
extern BigInt pow (BigInt x, ll p);
void decode (int n, int l, int x[]) {
BigInt res (0), rep (0);
vector<int> ans (n);
sort(x, x+l);
for (int i = x[l-2]; i < x[l-1]; i++) res = res + 1;
int last = 0;
for (int i = 0; i < l-1; i++) for (; last < x[i]; last++) res = res + ncr[254-last+n*5-i][n*5-i-1];
for (int i = n-1; i >= 0; i--) {
while (rep + BigInt(ans[i]+1) * pow(BigInt(256), i) <= res) ans[i]++;
rep = rep + BigInt(ans[i]) * pow(BigInt(256), i);
}
for (int i = 0; i < n; i++) output(ans[i]);
}