제출 #1356059

#제출 시각아이디문제언어결과실행 시간메모리
1356059Jawad_Akbar_JJ앵무새 (IOI11_parrots)C++17
100 / 100
1412 ms68532 KiB
#include <iostream>
#include <vector>
#include "encoderlib.h"

using namespace std;
namespace {
	#define ll __int128
	const int N = 600;

	struct Int{
		ll M = 1e30, L = 15, S = 6;
		vector<ll> Me = vector<ll> (S, 0);
		

		void operator=(string s){
			ll k = s.size();
			for (ll i=1, num = 0, p = 1;i<=k;i++){
				num += p * (s[k-i] - '0');
				p *= 10;
				if (i % L == 0)
					Me[i / L - 1] = num, num = 0, p = 1;
				else if (i == k)
					Me[i / L] = num;
			}
		}

		void operator+=(Int A){
			Int C;
			for (ll i=0, cr = 0;i<S;i++){
				C.Me[i] = Me[i] + A.Me[i] + cr, cr = 0;
				if (C.Me[i] >= M)
					C.Me[i] -= M, cr = 1;
			}
			swap(C.Me, Me);
		}

		void operator-=(Int A){
			Int C;
			for (ll i=0, cr = 0;i<S;i++){
				C.Me[i] = Me[i] - A.Me[i] - cr, cr = 0;
				if (C.Me[i] < 0)
					C.Me[i] += M, cr = 1;
			}
			swap(C.Me, Me);
		}
		void operator*=(int A){
			Int C;
			for (ll i=0, cr = 0;i<S;i++){
				Me[i] = Me[i] * A + cr, cr = 0;
				if (Me[i] >= M)
					cr = Me[i] / M, Me[i] %= M; 
			}
		}
		bool operator<(Int A){
			for (ll i=S-1;i + 1;i--){
				if (Me[i] != A.Me[i])
					return Me[i] < A.Me[i];
			}
			return 0;
		}
	};

	Int Ch[N][N];
}

void encode(int n, int M[]){
	for (int i=1;i<N;i++){
		Ch[i-1][0] = "1";
		for (int j=1;j<N;j++){
			Ch[i][j].Me = Ch[i-1][j-1].Me;
			Ch[i][j] += Ch[i-1][j];
		}
	}
	Int Inp, tfs, tmp;
	tfs = "256", Inp = "0";
	for (int i=0;i<n;i++){
		Inp *= 256;
		tmp = to_string(M[i]);
		Inp += tmp;
		// Inp.Print();
	}
	Inp.Me[0]++;
	// Inp.Print();

	int W = min(300, 5 * n), H = 255, B = 0;
	while (W > 0 and H > 0){
		if (Ch[W-1+H][H] < Inp)
			Inp -= Ch[W - 1+H][H], H--, B++;
		else
			W--, send(B);
	}
	while (W--)
		send(B);

}
#include <iostream>
#include <vector>
#include <algorithm>
#include "decoderlib.h"

using namespace std;
namespace {
	#define ll __int128
	const int N = 600;

	struct Int{
		ll M = 1e30, L = 9, S = 6;
		vector<ll> Me = vector<ll> (S, 0);
		

		void operator=(string s){
			ll k = s.size();
			for (ll i=1, num = 0, p = 1;i<=k;i++){
				num += p * (s[k-i] - '0');
				p *= 10;
				if (i % L == 0)
					Me[i / L - 1] = num, num = 0, p = 1;
				else if (i == k)
					Me[i / L] = num;
			}
		}

		void operator+=(Int A){
			Int C;
			for (ll i=0, cr = 0;i<S;i++){
				C.Me[i] = Me[i] + A.Me[i] + cr, cr = 0;
				if (C.Me[i] >= M)
					C.Me[i] -= M, cr = 1;
			}
			swap(C.Me, Me);
		}

		void operator-=(Int A){
			Int C;
			for (ll i=0, cr = 0;i<S;i++){
				C.Me[i] = Me[i] - A.Me[i] - cr, cr = 0;
				if (C.Me[i] < 0)
					C.Me[i] += M, cr = 1;
			}
			swap(C.Me, Me);
		}
		void operator*=(Int A){
			Int C;
			for (ll i=0;i<S;i++){
				for (ll j=0, cr = 0, X;j<S;j++){
					X = Me[i] * A.Me[j] + cr, cr = X / M, X %= M;
					if (i + j < S)
						C.Me[i+j] += X;
				}
			}
			for (ll i=0;i<S-1;i++)
				C.Me[i+1] += C.Me[i] / M, C.Me[i] %= M;
			swap(C.Me, Me);
		}
		void operator/=(int k){
			for (ll i=S-1, cr = 0;i + 1;i--){
				cr = cr * M + Me[i];
				Me[i] = cr / k;
				cr %= k;
			}
		}
		bool operator<(Int A){
			for (ll i=S-1;i + 1;i--){
				if (Me[i] != A.Me[i])
					return Me[i] < A.Me[i];
			}
			return 0;
		}
	};

	Int Ch[N][N];
}
void decode(int n, int l, int X[]){
	for (int i=1;i<N;i++){
		Ch[i-1][0] = "1";
		for (int j=1;j<N;j++){
			Ch[i][j].Me = Ch[i-1][j-1].Me;
			Ch[i][j] += Ch[i-1][j];
		}
	}
	Int Inp, tfs, tmp;
	tfs = "256", Inp = "0";
	sort(X, X + l);

	int W = min(300, 5 * n), H = 255, B = 0;
	for (int i=0;i<l;i++){
		// cout<<X[i]<<' ';
		while (X[i] > B)
			Inp += Ch[W - 1 + H][H], H--, B++;
		W--;
	}
	// Inp.Print();
	vector<int> ans;
	for (int i=0;i<n;i++){
		ans.push_back(Inp.Me[0] & 255);
		Inp /= 256;
	}
	// cout<<endl;
	for (int i=1;i<=n;i++)
		output(ans[n - i]);
	// , cout<<ans[n - i]<<' ';
	// cout<<endl;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…