oj.uz

답안 #873722

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
873722 2023-11-15T14:29:47 Z 12345678 앵무새 (IOI11_parrots) C++17
0 / 100
 2000 ms 264036 KB 
#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
const int nx=70, kx=256;

struct bignum
{
	vector<ll> val;
	bignum(): val(nx, 0){}
	bignum(ll x)
	{
		val.assign(nx, 0);
		for (int i=0; i<nx&&x>0; i++)
		{
			val[i]=x%kx;
			x/=kx;
		}
	}
	bignum &operator+=(const bignum &rhs)
	{
		ll carry=0;
		for (int i=0; i<nx; i++)
		{
			val[i]+=rhs.val[i]+carry;
			carry=val[i]/kx;
			val[i]-=carry*kx;
		}
		return *this;
	}
	bignum &operator-=(const bignum &rhs)
	{
		ll carry=0;
		for (int i=0; i<nx; i++)
		{
			val[i]-=rhs.val[i]+carry;
			carry=0;
			if (val[i]<0) {
				val[i]+=kx;
				carry++;
			}
		}
		return *this;
	}
	bignum &operator*=(const ll &rhs)
	{
		ll carry=0;
		for (int i=0; i<nx; i++)
		{
			val[i]*=rhs;
			val[i]+=carry;
			carry=val[i]/kx;
			val[i]-=carry*kx;
		}
		return *this;
	}
	friend bignum operator+(const bignum &lhs, const bignum &rhs) {return bignum(lhs)+=rhs;}
	friend bignum operator-(const bignum &lhs, const bignum &rhs) {return bignum(lhs)+=rhs;}
	friend bignum operator*(const bignum &lhs, const ll &rhs) {return bignum(lhs)*=rhs;}
	friend bignum operator*(const ll &lhs, const bignum &rhs) {return bignum(rhs)*=lhs;}
	int cmp(const bignum &rhs) {
		for (int i=nx-1; i>=0; i--)
		{
			if (val[i]<rhs.val[i]) return -1;
			if (val[i]>rhs.val[i]) return 1;
		}
		return 0;
	}
	bool operator<(const bignum &rhs) {return cmp(rhs)==-1;}
	bool operator>(const bignum &rhs) {return cmp(rhs)==1;}
	bool operator<=(const bignum &rhs) {return cmp(rhs)!=1;}
	bool operator>=(const bignum &rhs) {return cmp(rhs)!=-1;}
	bool operator==(const bignum &rhs) {return cmp(rhs)==0;}
	bool operator!=(const bignum &rhs) {return cmp(rhs)!=0;}
	string to_str()
	{
		auto res=val;
		while (res.size()>1&&res.back()==0) res.pop_back();
		reverse(res.begin(), res.end());
		string s="";
		for (auto x:res) s+=to_string(x)+" ";
		s.pop_back();
		return s;
	}
};


void encode(int N, int M[])
{
    bignum vl, tmp;
    vector<vector<bignum>> dp(580, vector<bignum> (580));
    for (int i=0; i<N; i++) vl.val[i]=M[N-1-i];
    for (int i=0; i<580; i++)
    {
        for (int j=0; j<=i; j++)
        {
            if (j==0||j==i) dp[i][j].val[0]=1;
            else dp[i][j]=dp[i-1][j]+dp[i-1][j-1];
            //cout<<i<<' '<<j<<'\n';
            //cout<<dp[i][j].to_str()<<'\n';
        }
    }
    vector<int> s(kx+1);
    int left=320;
    //cout<<vl.to_str()<<'\n';
    for (int i=0; i<kx; i++)
    {
        tmp=0;
        for (int j=left; j>=0; j--)
        {
            if (dp[kx-i-1+left-j][kx-i-1]+tmp>vl)
            {
                vl-=tmp;
                s[i]=j;
                left-=j;
                break;
            }
            tmp+=dp[kx-i-1+left-j][kx-i-1];
            //if (i==1) cout<<"here"<<' '<<j<<' '<<tmp.to_str()<<'\n';
        }
        //cout<<i<<' '<<s[i]<<'\n';
        //if (i==0) cout<<vl.to_str()<<'\n';
        //if (i==0) cout<<tmp.to_str()<<'\n';
    }
    s[kx]=left;
    for (int i=0; i<kx; i++) for (int j=0; j<s[i+1]; j++) send(i);
    for (int i=0; i<kx+1; i++)
    {
        //if (s[i]!=0) printf("%d %d\n", i, s[i]);
    }
}

#include "decoder.h"
#include "decoderlib.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
const int nx=70, kx=256;

struct bignum
{
	vector<ll> val;
	bignum(): val(nx, 0){}
	bignum(ll x)
	{
		val.assign(nx, 0);
		for (int i=0; i<nx&&x>0; i++)
		{
			val[i]=x%kx;
			x/=kx;
		}
	}
	bignum &operator+=(const bignum &rhs)
	{
		ll carry=0;
		for (int i=0; i<nx; i++)
		{
			val[i]+=rhs.val[i]+carry;
			carry=val[i]/kx;
			val[i]-=carry*kx;
		}
		return *this;
	}
	bignum &operator-=(const bignum &rhs)
	{
		ll carry=0;
		for (int i=0; i<nx; i++)
		{
			val[i]-=rhs.val[i]+carry;
			carry=0;
			if (val[i]<0) {
				val[i]+=kx;
				carry++;
			}
		}
		return *this;
	}
	bignum &operator*=(const ll &rhs)
	{
		ll carry=0;
		for (int i=0; i<nx; i++)
		{
			val[i]*=rhs;
			val[i]+=carry;
			carry=val[i]/kx;
			val[i]-=carry*kx;
		}
		return *this;
	}
	friend bignum operator+(const bignum &lhs, const bignum &rhs) {return bignum(lhs)+=rhs;}
	friend bignum operator-(const bignum &lhs, const bignum &rhs) {return bignum(lhs)+=rhs;}
	friend bignum operator*(const bignum &lhs, const ll &rhs) {return bignum(lhs)*=rhs;}
	friend bignum operator*(const ll &lhs, const bignum &rhs) {return bignum(rhs)*=lhs;}
	int cmp(const bignum &rhs) {
		for (int i=nx-1; i>=0; i--)
		{
			if (val[i]<rhs.val[i]) return -1;
			if (val[i]>rhs.val[i]) return 1;
		}
		return 0;
	}
	bool operator<(const bignum &rhs) {return cmp(rhs)==-1;}
	bool operator>(const bignum &rhs) {return cmp(rhs)==1;}
	bool operator<=(const bignum &rhs) {return cmp(rhs)!=1;}
	bool operator>=(const bignum &rhs) {return cmp(rhs)!=-1;}
	bool operator==(const bignum &rhs) {return cmp(rhs)==0;}
	bool operator!=(const bignum &rhs) {return cmp(rhs)!=0;}
    /*
	string to_str()
	{
		auto res=val;
		while (res.size()>1&&res.back()==0) res.pop_back();
		reverse(res.begin(), res.end());
		string s="";
		for (auto x:res) s+=to_string(x)+" ";
		s.pop_back();
		return s;
	}*/
};

void decode(int N, int L, int X[])
{
    bignum res=0;
    int sm=0;
    vector<int> s(kx+1, 0);
    for (int i=0; i<L; i++) s[X[i]+1]++, sm++;
    s[0]=320-sm;
    vector<vector<bignum>> dp(580, vector<bignum> (580));
    for (int i=0; i<580; i++)
    {
        for (int j=0; j<=i; j++)
        {
            if (j==0||j==i) dp[i][j].val[0]=1;
            else dp[i][j]=dp[i-1][j]+dp[i-1][j-1];
        }
    }
    int left=320;
    for (int i=0; i<kx; i++)
    {
        for (int j=left; j>s[i]; j--)
        {
            res+=dp[kx-i-1+left-j][kx-i-1];
        }
        left-=s[i];
        //cout<<i<<' '<<left<<'\n';
    }
    res+=s[kx];
    vector<int> ans(N);
    for (int i=0; i<N; i++) ans[N-1-i]=res.val[i];
    for (int i=0; i<N; i++) output(ans[i]);
    //cout<<"here"<<res.to_str()<<'\n';
}

/*
10
1 1 2 1 2 3 1 7 10 9
*/

Subtask #1
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 776 ms 264036 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2056 ms 198828 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2056 ms 198516 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2041 ms 198808 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2059 ms 198832 KB Time limit exceeded
2 Execution timed out 2045 ms 198352 KB Time limit exceeded
3 Execution timed out 2055 ms 198680 KB Time limit exceeded
4 Execution timed out 2020 ms 198624 KB Time limit exceeded
5 Execution timed out 2072 ms 198588 KB Time limit exceeded
6 Execution timed out 2080 ms 198364 KB Time limit exceeded
7 Execution timed out 2056 ms 198384 KB Time limit exceeded