| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 116798 | dragonslayerit | 앵무새 (IOI11_parrots) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "decoder.h"
#include "decoderlib.h"
#include <vector>
#include <cassert>
#include <string>
namespace{
struct BigNum{
//LSB first
std::vector<int> digits;
BigNum(){
}
BigNum(int num):digits({num}){
normalize();
}
BigNum(std::string num){
for(int i=0;i<num.size();i++){
*this+=*this+*this+*this+*this;
*this+=*this;
*this+=BigNum(num[i]-'0');
}
}
BigNum(const char* num){
for(int i=0;num[i];i++){
*this+=*this+*this+*this+*this;
*this+=*this;
*this+=BigNum(num[i]-'0');
}
}
BigNum& normalize(){
int carry=0;
for(int i=0;i<digits.size();i++){
digits[i]+=carry;
int mod=digits[i]&255;
int div=(digits[i]-mod)>>8;
carry=div;
digits[i]=mod;
}
assert(carry>=0);
assert(carry<256);
if(carry){
digits.push_back(carry);
}
while(digits.size()&&digits.back()==0) digits.pop_back();
return *this;
}
BigNum& operator+=(BigNum num){
if(digits.size()<num.digits.size()) std::swap(digits,num.digits);
for(int i=0;i<num.digits.size();i++){
digits[i]+=num.digits[i];
}
return normalize();
}
BigNum& operator-=(BigNum num){
assert(digits.size()>=num.digits.size());
for(int i=0;i<num.digits.size();i++){
digits[i]-=num.digits[i];
}
return normalize();
}
BigNum operator+(BigNum num)const{
return num+=*this;
}
bool operator<(BigNum num)const{
if(digits.size()!=num.digits.size()) return digits.size()<num.digits.size();
for(int i=(int)digits.size()-1;i>=0;i--){
if(digits[i]!=num.digits[i]){
return digits[i]<num.digits[i];
}
}
return false;
}
bool operator==(BigNum num)const{
return !(*this<num)&&!(num<*this);
}
bool operator!=(BigNum num)const{
return !(*this==num);
}
void hexdump(){
for(int i=(int)digits.size()-1;i>=0;i--){
fprintf(stderr,"%02x",digits[i]);
}
}
};
struct BigNum pascal[400][400];
}
void decode(int N, int L, int X[])
{
for(int i=0;i<=N*2;i++){
pascal[i][0]=BigNum(1);
}
for(int j=0;j<=255;j++){
pascal[0][i]=BigNum(1);
}
for(int i=1;i<=N*2;i++){
for(int j=1;j<=255;j++){
pascal[i][j]=pascal[i-1][j]+pascal[i][j-1];
}
}
std::vector<int> cnt(256);
for(int i=0;i<L;i++){
cnt[X[i]]++;
}
std::vector<int> bits;
for(int i=0;i<256;i++){
while(cnt[i]--){
bits.push_back(0);
}
bits.push_back(1);
}
bits.pop_back();
/*
fprintf(stderr,"D:");
for(int x:bits){
fprintf(stderr,"%d",x);
}
fprintf(stderr,"\n");
*/
struct BigNum num;
int zeros=0,ones=0;
for(int i=(int)bits.size()-1;i>=0;i--){
if(bits[i]){
ones++;
if(zeros>0){
//fprintf(stderr,"Add "),pascal[zeros-1][ones].hexdump(),fprintf(stderr,"\n");
num+=pascal[zeros-1][ones];
}
}else{
zeros++;
}
}
//num.hexdump(),fprintf(stderr,"\n");
num.digits.resize(N);
for(int i=0;i<N;i++){
output(num.digits[i]);
}
}