Submission #322563

#	Time	Username	Problem	Language	Result	Execution time	Memory
322563		CaroLinda	Parrots (IOI11_parrots)	C++14	100 / 100	151 ms	41760 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>
 
#define all(x) x.begin(),x.end()
#define ll long long
#define sz(x) (int)(x.size() )
#define CTE 29
 
const int BASE = (1<<CTE);
 
using namespace std ;
 
struct bignum
{
	vector<int> a ;
  
	void trim() 
	{
		while( sz(a) > 0 && a.back() == 0 ) a.pop_back() ;
	}
 
	bignum operator + (bignum other) const
	{
		bignum aux ;
 
		for(int i = 0 , carry = 0 ; i < max(sz(other.a), sz(a)) || carry ; i++ )
		{
			int addOther = (i >= sz(other.a) ) ? 0 : other.a[i] ;
			int addThis = (i >= sz(a) ) ? 0 : a[i] ;
 
			aux.a.push_back( addOther + addThis + carry ) ;
 
			carry = ( aux.a.back() >= BASE ) ;
 
			if(carry) aux.a.back() -= BASE ;
 
		}
 
		return aux ;
 
	}
 
	bool operator < ( bignum other ) const 
	{
		if( sz(a) != sz(other.a) ) return sz(a) < sz(other.a) ;
 
		for(int i = sz(a) - 1 ; i >= 0 ; i-- )
			if( a[i] != other.a[i] ) return a[i] < other.a[i] ;
 
	 	return false ;
	}
 
	bool operator == (bignum other) const  
	{
		return !(*this < other) && !(other < *this) ;
	}
 
	bool operator <= (bignum other) { return !(other < *this ) ; }
 
	bignum operator - (bignum other )const 
	{
		bignum aux ;
 
		for(int i = 0 ,carry=0 ; i < max(sz(a), sz(other.a) )  ; i++ )
		{
 
			int myNumber = ( i >= sz(a) ) ? 0 : a[i] ;
			int otherNumber = ( i >= sz(other.a) ) ? 0 : other.a[i] ;
 
			aux.a.push_back( myNumber - otherNumber - carry ) ;
 
			carry = ( aux.a.back() < 0 ) ;
 
			if(carry ) aux.a.back() += BASE ;
 
		}
 
		aux.trim() ;
		return aux ;
 
	}
 
} ;
 
static bool isFirst = true ;
static vector< vector<bignum> > bin(600, vector<bignum>(600) ) ;

void encode(int N, int M[])
{
 
	vector<int> ans(64*8,0) ;
 
	for(int i = 0, filling = 0  ; i < N ; i++ )
	{
 
		for(int j= 0 ; j < 8 ; j++ , filling++ )
			if( (M[i]&(1<<j) ) != 0 )  ans[filling] = 1 ;
	}
 
	bignum num ;
 
	for(int i = 0 ; i < sz(ans) ; )
	{
 
		int j = i , curNum = 0 ;
 
		while( j < sz(ans) && j-i < CTE ) 
		{
			curNum |= (1<<(j-i)) * ans[j] ;
			j++ ;
		}
 
		i = j ;
	
	   num.a.push_back(curNum ) ;
 
	}
 
 	if(isFirst)
 	{
		for(int i = 0 ; i <= 576 ; i++ )
		{
			bin[i][0].a.push_back(1) ;
			for(int j = 1 ; j <= i ; j++ ) bin[i][j] = bin[i-1][j-1] + bin[i-1][j] ;
		}
		isFirst = false ;
	}
 
	int MAX = 256 + 5*N ;
 
	num.trim() ;
 
	bignum toAdd ;
	toAdd.a.push_back(1) ;
 
	num = num + toAdd ;
 
	int separatorsLeft = 256 ;
	vector<int> myString(MAX, 0 ) ;
 
	for(int i = 0 ; i < MAX && separatorsLeft ; i++ )
	{
		if( bin[MAX-1-i][separatorsLeft] < num )
		{
			num = num - bin[MAX-i-1][separatorsLeft] ;
			myString[i] = 1 ;
			separatorsLeft-- ;
		}			
	}
 
 	for(int i = 0 , cnt = 0; i < MAX && cnt < 256 ; cnt++  )
 	{
	
 		int j = i ;
 		while( j < MAX && myString[j] == 0 ) j++ ;
 
 		for(int g = 0 ; g < j-i ; g++ ) send(cnt) ;
 
 		i = j + 1 ;
 	}         
 
	
}

decoder

#include "decoder.h"
#include "decoderlib.h"
#include <bits/stdc++.h>
 
#define all(x) x.begin(),x.end()
#define ll long long
#define sz(x) (int)(x.size() )
#define CTE 29
 
const int BASE = (1<<CTE);
 
using namespace std ;
 
struct bignum
{
	vector<int> a ;
 
	void print()
	{
		cout << "Printing this shit" << endl ;
		for(auto e : a ) cout << e << " " ;
		cout << endl ;
	}
 
	void trim() 
	{
		while( sz(a) > 0 && a.back() == 0 ) a.pop_back() ;
	}
 
	bignum operator + (bignum other) const
	{
		bignum aux ;
 
		for(int i = 0 , carry = 0 ; i < max(sz(other.a), sz(a)) || carry ; i++ )
		{
			int addOther = (i >= sz(other.a) ) ? 0 : other.a[i] ;
			int addThis = (i >= sz(a) ) ? 0 : a[i] ;
 
			aux.a.push_back( addOther + addThis + carry ) ;
 
			carry = ( aux.a.back() >= BASE ) ;
 
			if(carry) aux.a.back() -= BASE ;
 
		}
 
		return aux ;
 
	}
 
	bool operator < ( bignum other ) const 
	{
		if( sz(a) != sz(other.a) ) return sz(a) < sz(other.a) ;
 
		for(int i = sz(a) - 1 ; i >= 0 ; i-- )
			if( a[i] != other.a[i] ) return a[i] < other.a[i] ;
 
	 	return false ;
	}
 
	bool operator == (bignum other) const  
	{
		return !(*this < other) && !(other < *this) ;
	}
 
	bool operator <= (bignum other) { return !(other < *this ) ; }
 
	bignum operator - (bignum other )const 
	{
		bignum aux ;
 
		for(int i = 0 ,carry=0 ; i < max(sz(a), sz(other.a) )  ; i++ )
		{
 
			int myNumber = ( i >= sz(a) ) ? 0 : a[i] ;
			int otherNumber = ( i >= sz(other.a) ) ? 0 : other.a[i] ;
 
			aux.a.push_back( myNumber - otherNumber - carry ) ;
 
			carry = ( aux.a.back() < 0 ) ;
 
			if(carry ) aux.a.back() += BASE ;
 
		}
 
		aux.trim() ;
		return aux ;
 
	}
 
} ;

static bool isFirst = true ; 
static vector< vector<bignum> > bin(600, vector<bignum>(600) ) ;

void decode(int N, int L, int X[])
{
 
 
	if(isFirst)
	{
		for(int i = 0 ; i < 577 ; i++ )
		{
			bin[i][0].a.push_back(1) ;
			for(int j = 1 ; j <= i ; j++ ) bin[i][j] = bin[i-1][j-1] + bin[i-1][j] ;
		}
		isFirst = false ;
	}
 
	int MAX = 5*N + 256 ;
 
	vector<int> freq(257 , 0 ) ;
 
	for(int i= 0 ; i < L ; i++ ) freq[ X[i] ]++ ;
 
	vector<int> myString(MAX,0) ;
 
	int cnt = 0 ;
 
	for(int i = 1 ; i <= 256 ; i++ )
	{
		cnt += freq[i-1] ;
		myString[cnt] = 1 ;
		cnt++ ;	
	}
 
	bignum num ;
 
	int separatorsLeft = 256 ;
 
	for(int i = 0 ; i < MAX  ; i++ )
	{
		if( myString[i] == 0 ) continue ;
		num = num + bin[MAX-1-i][separatorsLeft] ;		
		separatorsLeft-- ;
	}	
 
	num.trim() ;
 
	vector<int> ans(8*N,0) ;
 
	int curBit = 0 ;
 
	for(int i : num.a )
	{
		for(int j = 0  ; j < CTE ; j++, curBit++ )
			if( (i&(1<<j) ) != 0 ) ans[curBit] = 1 ;		
	}
 
	for(int i = 0 ; i < sz(ans) ;) 
	{
		int val = 0 ;
 
		for(int j = 0 ; j < 8 ; j++ , i++ )
			val += (1<<j) * ans[i] ;
 
		output(val) ;
 
	}	
	
}

• Subtask 1: 17 / 17
• Subtask 2: 17 / 17
• Subtask 3: 18 / 18
• Subtask 4: 29 / 29
• Subtask 5: 19 / 19