oj.uz

Submission #761039

# Submission time Handle Problem Language Result Execution time Memory
761039 2023-06-19T06:11:20 Z SanguineChameleon Parrots (IOI11_parrots) C++17
100 / 100
 1140 ms 259656 KB 
#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);
	}
}

#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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 534 ms 259072 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 541 ms 259444 KB Output is correct
2 Correct 542 ms 259428 KB Output is correct
3 Correct 552 ms 259480 KB Output is correct
4 Correct 619 ms 259524 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 556 ms 259484 KB Output is correct
2 Correct 544 ms 259400 KB Output is correct
3 Correct 556 ms 259496 KB Output is correct
4 Correct 554 ms 259408 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 548 ms 259416 KB Output is correct
2 Correct 554 ms 259416 KB Output is correct
3 Correct 558 ms 259528 KB Output is correct
4 Correct 587 ms 259408 KB Output is correct
5 Correct 601 ms 259468 KB Output is correct
6 Correct 628 ms 259468 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 563 ms 259416 KB Output is correct - P = 1.750000
2 Correct 621 ms 259536 KB Output is correct - P = 2.437500
3 Correct 602 ms 259528 KB Output is correct - P = 2.484848
4 Correct 838 ms 259656 KB Output is correct - P = 3.280000
5 Correct 1049 ms 259480 KB Output is correct - P = 3.833333
6 Correct 1131 ms 259612 KB Output is correct - P = 4.015873
7 Correct 1140 ms 259596 KB Output is correct - P = 4.078125