# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
923116 | daoquanglinh2007 | 앵무새 (IOI11_parrots) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "decoder.h"
#include "decoderlib.h"
#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>
using namespace std;
#define isz(a) (int)(a).size()
const int NM = 64, base = 128;
int N, L, M[NM+5], X[5*NM+5];
string dp[5*NM+5][256];
string create(int x){
string s = "";
while (x > 0){
s = char(x%base)+s;
x /= base;
}
if (s == "") s.push_back(0);
return s;
}
int decreate(string s){
int x = 0;
for (int i = 0; i < isz(s); i++)
x = x*base+s[i];
return x;
}
int cmp(string a, string b){
if (isz(a) < isz(b)) return -1;
if (isz(a) > isz(b)) return 1;
if (a < b) return -1;
if (a > b) return 1;
return 0;
}
string add(string a, string b){
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
while (isz(a) < isz(b)) a.push_back(0);
while (isz(b) < isz(a)) b.push_back(0);
string c = "";
int carry = 0;
for (int i = 0; i < isz(a); i++){
int s = a[i]+b[i]+carry;
c.push_back(s%base);
carry = s/base;
}
if (carry > 0) c.push_back(1);
reverse(c.begin(), c.end());
return c;
}
string sub(string a, string b){
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
while (isz(a) < isz(b)) a.push_back(0);
while (isz(b) < isz(a)) b.push_back(0);
string c = "";
int borrow = 0;
for (int i = 0; i < isz(a); i++){
int h = a[i]-b[i]-borrow;
if (h < 0){
h += base;
borrow = 1;
}
else{
borrow = 0;
}
c.push_back(h);
}
while (isz(c) > 1 && c[isz(c)-1] == 0) c.erase(isz(c)-1, 1);
reverse(c.begin(), c.end());
return c;
}
void preprocess(){
for (int i = 255; i >= 0; i--){
dp[5*N][i] = create(256-i);
}
for (int i = 5*N-1; i >= 1; i--)
for (int j = 255; j >= 0; j--){
dp[i][j] = dp[i+1][j];
if (j < 255) dp[i][j] = add(dp[i][j], dp[i][j+1]);
}
}
string mul(string a, int b){
string c = "";
int carry = 0;
for (int i = isz(a)-1; i >= 0; i--){
int s = a[i]*b+carry;
c.push_back(s%base);
carry = s/base;
}
while (carry > 0){
c.push_back(carry%base);
carry /= base;
}
while (isz(c) > 1 && c[isz(c)-1] == 0) c.erase(isz(c)-1, 1);
reverse(c.begin(), c.end());
return c;
}
void trace(int i, string s){
if (i > 5*N) return;
for (int j = 255; j >= 0; j--){
if (cmp(dp[i][j], s) >= 0){
send(j);
if (j < 255) s = sub(s, dp[i][j+1]);
trace(i+1, s);
return;
}
}
}
void encode(int _N, int _M[]){
N = _N;
for (int i = 0; i < N; i++) M[i] = _M[i];
preprocess();
string tmp = create(0);
for (int i = 0; i < N; i++){
tmp = add(mul(tmp, 256), create(M[i]));
}
trace(1, tmp);
}
string find_order(int i){
if (i > 5*N) return create(1);
string res = create(0);
if (X[i] < 255) res = dp[i][X[i]+1];
return add(res, find_order(i+1));
}
string div(string a, int b){
string c = "";
int h = 0;
for (int i = 0; i < isz(a); i++){
h = h*base+a[i];
c.push_back(h/b);
h %= b;
}
reverse(c.begin(), c.end());
while (isz(c) > 1 && c[isz(c)-1] == 0) c.erase(isz(c)-1, 1);
reverse(c.begin(), c.end());
return c;
}
int mod(string a, int b){
string c = "";
int h = 0;
for (int i = 0; i < isz(a); i++){
h = (h*base+a[i])%b;
}
return h;
}
void decode(int _N, int _L, int _X[]){
N = _N;
L = _L;
for (int i = 5*N; i >= 1; i--) X[i] = _X[i-1];
sort(X+1, X+1+5*N);
preprocess();
string tmp = find_order(1);
for (int i = N-1; i >= 0; i--){
M[i] = mod(tmp, 256);
tmp = div(tmp, 256);
}
for (int i = 0; i < N; i++) output(M[i]);
}
#include "decoder.h"
#include "decoderlib.h"
#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>
using namespace std;
#define isz(a) (int)(a).size()
const int NM = 64, base = 128;
int N, L, M[NM+5], X[5*NM+5];
string dp[5*NM+5][256];
string create(int x){
string s = "";
while (x > 0){
s = char(x%base)+s;
x /= base;
}
if (s == "") s.push_back(0);
return s;
}
int decreate(string s){
int x = 0;
for (int i = 0; i < isz(s); i++)
x = x*base+s[i];
return x;
}
int cmp(string a, string b){
if (isz(a) < isz(b)) return -1;
if (isz(a) > isz(b)) return 1;
if (a < b) return -1;
if (a > b) return 1;
return 0;
}
string add(string a, string b){
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
while (isz(a) < isz(b)) a.push_back(0);
while (isz(b) < isz(a)) b.push_back(0);
string c = "";
int carry = 0;
for (int i = 0; i < isz(a); i++){
int s = a[i]+b[i]+carry;
c.push_back(s%base);
carry = s/base;
}
if (carry > 0) c.push_back(1);
reverse(c.begin(), c.end());
return c;
}
string sub(string a, string b){
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
while (isz(a) < isz(b)) a.push_back(0);
while (isz(b) < isz(a)) b.push_back(0);
string c = "";
int borrow = 0;
for (int i = 0; i < isz(a); i++){
int h = a[i]-b[i]-borrow;
if (h < 0){
h += base;
borrow = 1;
}
else{
borrow = 0;
}
c.push_back(h);
}
while (isz(c) > 1 && c[isz(c)-1] == 0) c.erase(isz(c)-1, 1);
reverse(c.begin(), c.end());
return c;
}
void preprocess(){
for (int i = 255; i >= 0; i--){
dp[5*N][i] = create(256-i);
}
for (int i = 5*N-1; i >= 1; i--)
for (int j = 255; j >= 0; j--){
dp[i][j] = dp[i+1][j];
if (j < 255) dp[i][j] = add(dp[i][j], dp[i][j+1]);
}
}
string mul(string a, int b){
string c = "";
int carry = 0;
for (int i = isz(a)-1; i >= 0; i--){
int s = a[i]*b+carry;
c.push_back(s%base);
carry = s/base;
}
while (carry > 0){
c.push_back(carry%base);
carry /= base;
}
while (isz(c) > 1 && c[isz(c)-1] == 0) c.erase(isz(c)-1, 1);
reverse(c.begin(), c.end());
return c;
}
void trace(int i, string s){
if (i > 5*N) return;
for (int j = 255; j >= 0; j--){
if (cmp(dp[i][j], s) >= 0){
send(j);
if (j < 255) s = sub(s, dp[i][j+1]);
trace(i+1, s);
return;
}
}
}
void encode(int _N, int _M[]){
N = _N;
for (int i = 0; i < N; i++) M[i] = _M[i];
preprocess();
string tmp = create(0);
for (int i = 0; i < N; i++){
tmp = add(mul(tmp, 256), create(M[i]));
}
trace(1, tmp);
}
string find_order(int i){
if (i > 5*N) return create(1);
string res = create(0);
if (X[i] < 255) res = dp[i][X[i]+1];
return add(res, find_order(i+1));
}
string div(string a, int b){
string c = "";
int h = 0;
for (int i = 0; i < isz(a); i++){
h = h*base+a[i];
c.push_back(h/b);
h %= b;
}
reverse(c.begin(), c.end());
while (isz(c) > 1 && c[isz(c)-1] == 0) c.erase(isz(c)-1, 1);
reverse(c.begin(), c.end());
return c;
}
int mod(string a, int b){
string c = "";
int h = 0;
for (int i = 0; i < isz(a); i++){
h = (h*base+a[i])%b;
}
return h;
}
void decode(int _N, int _L, int _X[]){
N = _N;
L = _L;
for (int i = 5*N; i >= 1; i--) X[i] = _X[i-1];
sort(X+1, X+1+5*N);
preprocess();
string tmp = find_order(1);
for (int i = N-1; i >= 0; i--){
M[i] = mod(tmp, 256);
tmp = div(tmp, 256);
}
for (int i = 0; i < N; i++) output(M[i]);
}