oj.uz

답안 #224033

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
224033 2020-04-17T05:28:50 Z Lawliet 앵무새 (IOI11_parrots) C++14
100 / 100
 173 ms 27832 KB 
#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXP = 330;
const int MAXL = 260;
const int MAXB = 520;
const int MAXV = 600;

class BigNum
{
	public:

		BigNum() : base( 1000000000 ) {}

		int size() { return num.size(); }
		int digit(int i) { return num[i]; }
		void insert(int k) { num.push_back( k ); }
		void change(int i, int k) { num[i] -= k; }

		BigNum operator + (BigNum& aux)
		{
			BigNum ans;

			BigNum A = aux;
			BigNum B = *this;

			if( A.size() < B.size() ) swap( A , B );

			while( B.size() != A.size() )
				B.insert( 0 );

			int acc = 0;

			for(int i = 0 ; i < B.size() ; i++)
			{
				ans.insert( A.digit(i) + B.digit(i) + acc );
				acc = 0;

				int curDigit = ans.digit(i);

				if( curDigit >= base )
				{
					acc = curDigit/base;
					ans.change( i , acc*base );
				}
			}

			if( acc > 0 ) ans.insert( acc );

			return ans;
		}

		bool operator <= (BigNum aux)
		{
			if( this->size() != aux.size() ) return this->size() < aux.size();

			for(int i = aux.size() - 1 ; i >= 0 ; i--)
				if( this->digit(i) != aux.digit(i) ) return this->digit(i) < aux.digit(i);

			return true;
		}

		bool operator < (BigNum aux)
		{
			if( this->size() != aux.size() ) return this->size() < aux.size();

			for(int i = aux.size() - 1 ; i >= 0 ; i--)
				if( this->digit(i) != aux.digit(i) ) return this->digit(i) < aux.digit(i);

			return false;
		}

	private:

		int base;

		vector< int > num;
};

bool hasInit = false;

BigNum pot[MAXB];
BigNum dp[MAXV][MAXL];

void buildPowers()
{
	pot[0].insert( 1 );

	for(int i = 1 ; i < MAXB ; i++)
		pot[i] = pot[i - 1] + pot[i - 1];
}

void buildBinomials()
{
	for(int i = 0 ; i < MAXV ; i++)
		dp[i][0].insert( 1 );

	for(int i = 1 ; i < MAXV ; i++)
		for(int j = 1 ; j <= i && j < MAXL ; j++)
			dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
}

void encode(int N, int M[])
{
	if( !hasInit )
	{
		buildPowers();
		buildBinomials();

		hasInit = true;
	}

	BigNum binary;

	for(int i = 0 ; i < N ; i++)
		for(int j = 0 ; j < 8 ; j++)
			if( M[i] & (1 << j) ) binary = binary + pot[ 8*i + j ];

	int remainParrots = 5*N;

	BigNum sum;

	for(int i = -1 ; i < 255 ; i++)
	{
		int qtdParrots;
		int qtdNumbers = 256 - i - 1;

		for(qtdParrots = 0 ; qtdParrots <= remainParrots ; qtdParrots++)
		{
			BigNum aux = sum;
			aux = aux + dp[ remainParrots - qtdParrots + qtdNumbers - 1 ][ qtdNumbers - 1 ];

			if( binary < aux ) break;

			sum = aux;
		}

		remainParrots -= qtdParrots;

		if( i == -1 ) continue;

		for(int j = 1 ; j <= qtdParrots ; j++)
			send( i );
	}

	while( remainParrots > 0 )
	{
		send( 255 );
		remainParrots--;
	}
}
#include "decoder.h"
#include "decoderlib.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXP = 330;
const int MAXL = 260;
const int MAXB = 520;
const int MAXV = 600;

class BigNum
{
	public:

		BigNum() : base( 1000000000 ) {}

		int size() { return num.size(); }
		int digit(int i) { return num[i]; }
		void insert(int k) { num.push_back( k ); }
		void change(int i, int k) { num[i] -= k; }

		BigNum operator + (BigNum& aux)
		{
			BigNum ans;

			BigNum A = aux;
			BigNum B = *this;

			if( A.size() < B.size() ) swap( A , B );

			while( B.size() != A.size() )
				B.insert( 0 );

			int acc = 0;

			for(int i = 0 ; i < B.size() ; i++)
			{
				ans.insert( A.digit(i) + B.digit(i) + acc );
				acc = 0;

				int curDigit = ans.digit(i);

				if( curDigit >= base )
				{
					acc = curDigit/base;
					ans.change( i , acc*base );
				}
			}

			if( acc > 0 ) ans.insert( acc );

			return ans;
		}

		bool operator <= (BigNum aux)
		{
			if( this->size() != aux.size() ) return this->size() < aux.size();

			for(int i = aux.size() - 1 ; i >= 0 ; i--)
				if( this->digit(i) != aux.digit(i) ) return this->digit(i) < aux.digit(i);

			return true;
		}

	private:

		int base;

		vector< int > num;
};

bool hasInit = false;

int freq[MAXL];

BigNum pot[MAXB];
BigNum dp[MAXV][MAXL];

void buildPowers()
{
	pot[0].insert( 1 );

	for(int i = 1 ; i < MAXB ; i++)
		pot[i] = pot[i - 1] + pot[i - 1];
}

void buildBinomials()
{
	for(int i = 0 ; i < MAXV ; i++)
		dp[i][0].insert( 1 );

	for(int i = 1 ; i < MAXV ; i++)
		for(int j = 1 ; j <= i && j < MAXL ; j++)
			dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
}

void decode(int N, int L, int X[])
{
	if( !hasInit )
	{
		buildPowers();
		buildBinomials();

		hasInit = true;
	}

	BigNum sum;

	int qtd = 5*N - L;

	for(int i = 0 ; i < qtd ; i++)
		sum = sum + dp[ 5*N - i + 256 ][ 256 ];

	for(int i = 0 ; i < L ; i++)
		freq[ X[i] ]++;

	int remainParrots = L;

	for(int i = 0 ; i < 255 ; i++)
	{
		int qtdNumbers = 256 - i - 1;

		while( freq[i] > 0 )
		{
			sum = sum + dp[ remainParrots + qtdNumbers - 1 ][ qtdNumbers - 1 ];

			freq[i]--;
			remainParrots--;
		}
	}

	BigNum cur;

	vector< int > binary;

	for(int i = 8*N - 1 ; i >= 0 ; i--)
	{
		BigNum aux = cur + pot[i];

		if( aux <= sum )
		{
			cur = aux;
			binary.push_back( 1 );
		}
		else binary.push_back( 0 );
	}

	reverse( binary.begin() , binary.end() );

	for(int i = 0 ; i < N ; i++)
	{
		int v = 0;

		for(int j = 0 ; j < 8 ; j++)
			if( binary[8*i + j] == 1 ) v += (1 << j);

		output( v );
	}
}

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 112 ms 26980 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 125 ms 27376 KB Output is correct
2 Correct 121 ms 27376 KB Output is correct
3 Correct 127 ms 27376 KB Output is correct
4 Correct 123 ms 27376 KB Output is correct

Subtask #3
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 117 ms 27632 KB Output is correct
2 Correct 124 ms 27376 KB Output is correct
3 Correct 124 ms 27632 KB Output is correct
4 Correct 124 ms 27376 KB Output is correct

Subtask #4
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 115 ms 27376 KB Output is correct
2 Correct 123 ms 27376 KB Output is correct
3 Correct 128 ms 27376 KB Output is correct
4 Correct 138 ms 27632 KB Output is correct
5 Correct 137 ms 27632 KB Output is correct
6 Correct 138 ms 27632 KB Output is correct

Subtask #5
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 123 ms 27632 KB Output is correct - P = 5.000000
2 Correct 163 ms 27632 KB Output is correct - P = 5.000000
3 Correct 137 ms 27632 KB Output is correct - P = 5.000000
4 Correct 158 ms 27632 KB Output is correct - P = 5.000000
5 Correct 165 ms 27632 KB Output is correct - P = 5.000000
6 Correct 170 ms 27832 KB Output is correct - P = 5.000000
7 Correct 173 ms 27632 KB Output is correct - P = 5.000000