Submission #761039

#	Time	Username	Problem	Language	Result	Execution time	Memory
761039		SanguineChameleon	Parrots (IOI11_parrots)	C++17	100 / 100	1140 ms	259656 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>
using namespace std;

namespace encoder {
	struct bignum {
		vector<int> digits;
		int len = 0;

		bignum() {}

		bignum(int X) {
			while (X) {
				digits.push_back(X & 1);
				X >>= 1;
			}
			len = digits.size();
		}

		void norm() {
			while (len > 0 && digits.back() == 0) {
				digits.pop_back();
				len--;
			}
		}

		int& operator[](int pos) {
			if (pos >= len) {
				digits.resize(pos + 1);
				len = pos + 1;
			}
			return digits[pos];
		}
	};

	ostream& operator<<(ostream &out, bignum B) {
		int X = 0;
		for (int i = B.len - 1; i >= 0; i--) {
			X = X << 1 | B[i];
		}
		out << X;
		return out;
	}

	bignum operator+(bignum B1, bignum B2) {
		bignum res;
		int len = max(B1.len, B2.len);
		int rem = 0;
		for (int i = 0; i < len; i++) {
			int sum = B1[i] + B2[i] + rem;
			res[i] = sum & 1;
			rem = sum >> 1;
		}
		if (rem) {
			res[len] = 1;
		}
		return res;
	}

	bignum operator-(bignum B1, bignum B2) {
		bignum res;
		int rem = 0;
		for (int i = 0; i < B1.len; i++) {
			int diff = B1[i] - B2[i] + rem;
			res[i] = diff & 1;
			rem = diff >> 1;
		}
		res.norm();
		return res;
	}

	bool operator>(bignum B1, bignum B2) {
		B1.norm();
		B2.norm();
		if (B1.len != B2.len) {
			return B1.len > B2.len;
		}
		for (int i = B1.len - 1; i >= 0; i--) {
			if (B1[i] != B2[i]) {
				return B1[i] > B2[i];
			}
		}
		return false;
	}

	const int maxL = 350;
	bignum dp[maxL][256];

	bool calc = false;
	
	vector<int> solve(int N, int M[]) {
		if (!calc) {
			for (int i = 0; i < 256; i++) {
				dp[0][i] = bignum(1);
			}
			for (int i = 1; i < maxL; i++) {
				dp[i][0] = bignum(1);
				for (int j = 1; j < 256; j++) {
					dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
				}
			}
			calc = true;
		}
		bignum msg;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < 8; j++) {
				msg[i << 3 | j] = (M[i] >> j) & 1;
			}
		}
		msg.norm();
		msg = msg + bignum(1);
		int len = 0;
		while (msg > dp[len][255]) {
			msg = msg - dp[len][255];
			len++;
		}
		vector<int> res;
		for (int i = len; i >= 1; i--) {
			for (int j = 0; j < 256; j++) {
				if (!(msg > dp[i][j])) {
					res.push_back(j);
					if (j > 0) {
						msg = msg - dp[i][j - 1];
					}
					break;
				}
			}
		}
		return res;
	}
}

void encode(int N, int M[]) {
	vector<int> res = encoder::solve(N, M);
	for (auto val: res) {
		send(val);
	}
}

decoder

#include "decoder.h"
#include "decoderlib.h"
#include <bits/stdc++.h>
using namespace std;

namespace decoder {
	struct bignum {
		vector<int> digits;
		int len = 0;

		bignum() {}

		bignum(int X) {
			while (X) {
				digits.push_back(X & 1);
				X >>= 1;
			}
			len = digits.size();
		}

		void norm() {
			while (len > 0 && digits.back() == 0) {
				digits.pop_back();
				len--;
			}
		}

		int& operator[](int pos) {
			if (pos >= len) {
				digits.resize(pos + 1);
				len = pos + 1;
			}
			return digits[pos];
		}
	};

	ostream& operator<<(ostream &out, bignum B) {
		int X = 0;
		for (int i = B.len - 1; i >= 0; i--) {
			X = X << 1 | B[i];
		}
		out << X;
		return out;
	}

	bignum operator+(bignum B1, bignum B2) {
		bignum res;
		int len = max(B1.len, B2.len);
		int rem = 0;
		for (int i = 0; i < len; i++) {
			int sum = B1[i] + B2[i] + rem;
			res[i] = sum & 1;
			rem = sum >> 1;
		}
		if (rem) {
			res[len] = 1;
		}
		return res;
	}

	bignum operator-(bignum B1, bignum B2) {
		bignum res;
		int rem = 0;
		for (int i = 0; i < B1.len; i++) {
			int diff = B1[i] - B2[i] + rem;
			res[i] = diff & 1;
			rem = diff >> 1;
		}
		res.norm();
		return res;
	}

	bool operator>(bignum B1, bignum B2) {
		B1.norm();
		B2.norm();
		if (B1.len != B2.len) {
			return B1.len > B2.len;
		}
		for (int i = B1.len - 1; i >= 0; i--) {
			if (B1[i] != B2[i]) {
				return B1[i] > B2[i];
			}
		}
		return false;
	}

	const int maxL = 350;
	bignum dp[maxL][256];

	bool calc = false;

	vector<int> solve(int N, int L, int X[]) {
		if (!calc) {
			for (int i = 0; i < 256; i++) {
				dp[0][i] = bignum(1);
			}
			for (int i = 1; i < maxL; i++) {
				dp[i][0] = bignum(1);
				for (int j = 1; j < 256; j++) {
					dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
				}
			}
			calc = true;
		}
		sort(X, X + L);
		bignum msg(0);
		for (int i = 0; i < L; i++) {
			msg = msg + dp[i][255];
		}
		for (int i = L - 1; i >= 0; i--) {
			if (X[i] > 0) {
				msg = msg + dp[i + 1][X[i] - 1];
			}
		}
		vector<int> res(N);
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < 8; j++) {
				res[i] |= (msg[i << 3 | j] << j);
			}
		}
		return res;
	}
}


void decode(int N, int L, int X[]) {
	vector<int> res = decoder::solve(N, L, X);
	for (auto val: res) {
		output(val);
	}
}

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