oj.uz

답안 #837273

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
837273 2023-08-25T08:55:41 Z pavement 앵무새 (IOI11_parrots) C++17
100 / 100
 551 ms 24024 KB 
#include "encoder.h"
#include "encoderlib.h"
#include <bitset>
#include <cassert>
#include <iostream>
#include <array>
using namespace std;

const int LEN = 514, LIM = 517;

static bitset<LEN> operator+ (const bitset<LEN> &lhs, const bitset<LEN> &rhs) {
	bitset<LEN> res;
	res.reset();
	bool carry = 0;
	for (int i = 0; i < LEN; i++) {
		res[i] = carry ^ lhs[i] ^ rhs[i];
		if ((carry && lhs[i]) || (carry && rhs[i]) || (lhs[i] && rhs[i])) {
			carry = 1;
		} else {
			carry = 0;
		}
	}
	assert(carry == 0);
	return res;
}

static bool fullSubtractor(bool b1, bool b2, bool& borrow) {
	bool diff;
	if (borrow) {
		diff = !(b1 ^ b2);
		borrow = !b1 || (b1 && b2);
	}
	else {
		diff = b1 ^ b2;
		borrow = !b1 && b2;
	}
	return diff;
}

static bitset<LEN> operator- (const bitset<LEN> &lhs, const bitset<LEN> &rhs) {
	bool borrow = 0;
	bitset<LEN> ans;
	ans.reset();
	for (int i = 0; i < LEN; i++) {
		ans[i] = fullSubtractor(lhs[i], rhs[i], borrow);
	}
	return ans;
}

bool lessThanOrEqualTo(const bitset<LEN> &lhs, const bitset<LEN> &rhs) {
	auto tmp = lhs ^ rhs;
	int pos = -1;
	for (int i = LEN - 1; i >= 0; i--) {
		if (tmp[i]) {
			pos = i;
			break;
		}
	}
	if (pos == -1 || rhs[pos]) return 1;
	else return 0;
}

static bitset<LEN> nck[LIM][LIM];

static void precompute_binomials() {
	for (int i = 0; i < LIM; i++) {
		for (int j = 0; j <= i; j++) {
			if (i == 0 || j == 0) {
				nck[i][j] = j == 0;
			} else {
				nck[i][j] = nck[i - 1][j] + nck[i - 1][j - 1];
			}
		}
	}
}

static bool init;

void encode(int N, int M[]) {
	int K = min(262, N * 5);
	if (!init) {
		precompute_binomials();
		init = 1;
	}
	bitset<LEN> cur;
	cur.reset();
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < 8; j++) {
			cur[i * 8 + j] = !!(M[i] & (1 << j));
		}
	}
	cur = cur + 1;
	for (int i = 0, val = 0; i < K; i++) {
		int len_left = K - 1 - i;
		while (1) {
			int vals_left = 255 - val;
			if (lessThanOrEqualTo(nck[len_left + vals_left][vals_left], cur)) {
				cur = cur - nck[len_left + vals_left][vals_left];
				val++;
			} else {
				break;
			}
		}
		send(val);
	}
}

#include "decoder.h"
#include "decoderlib.h"
#include <bitset>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <array>
using namespace std;

const int LEN = 514, LIM = 517;

static bitset<LEN> operator+ (const bitset<LEN> &lhs, const bitset<LEN> &rhs) {
	bitset<LEN> res;
	res.reset();
	bool carry = 0;
	for (int i = 0; i < LEN; i++) {
		res[i] = carry ^ lhs[i] ^ rhs[i];
		if ((carry && lhs[i]) || (carry && rhs[i]) || (lhs[i] && rhs[i])) {
			carry = 1;
		} else {
			carry = 0;
		}
	}
	assert(carry == 0);
	return res;
}

static bool fullSubtractor(bool b1, bool b2, bool &borrow) {
	bool diff = 0;
	if (borrow) {
		diff = !(b1 ^ b2);
		borrow = !b1 || (b1 && b2);
	} else {
		diff = b1 ^ b2;
		borrow = !b1 && b2;
	}
	return diff;
}

static bitset<LEN> operator- (const bitset<LEN> &lhs, const bitset<LEN> &rhs) {
	bool borrow = 0;
	bitset<LEN> ans;
	ans.reset();
	for (int i = 0; i < LEN; i++) {
		ans[i] = fullSubtractor(lhs[i], rhs[i], borrow);
	}
	return ans;
}

static bitset<LEN> nck[LIM][LIM];

static void precompute_binomials() {
	for (int i = 0; i < LIM; i++) {
		for (int j = 0; j <= i; j++) {
			if (i == 0 || j == 0) {
				nck[i][j] = j == 0;
			} else {
				nck[i][j] = nck[i - 1][j] + nck[i - 1][j - 1];
			}
		}
	}
}

static bool init;

void decode(int N, int L, int X[]) {
	if (!init) {
		precompute_binomials();
		init = 1;
	}
	sort(X, X + L);
	bitset<LEN> num(0);
	for (int i = 0; i < L; i++) {
		int len_left = L - i - 1;
		for (int val = i ? X[i - 1] : 0; val < X[i]; val++) {
			int val_left = 255 - val;
			num = num + nck[len_left + val_left][val_left];
		}
	}
	num = num - 1;
	for (int i = 0; i < N; i++) {
		int A = 0;
		for (int j = 0; j < 8; j++) {
			if (num[i * 8 + j]) {
				A |= (1 << j);
			}
		}
		output(A);
	}
}

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 517 ms 23848 KB Output is correct
2 Correct 508 ms 23752 KB Output is correct
3 Correct 496 ms 23788 KB Output is correct
4 Correct 512 ms 23764 KB Output is correct

Subtask #3
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 517 ms 23788 KB Output is correct
2 Correct 508 ms 23716 KB Output is correct
3 Correct 501 ms 23768 KB Output is correct
4 Correct 514 ms 23828 KB Output is correct

Subtask #4
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 501 ms 23720 KB Output is correct
2 Correct 521 ms 23708 KB Output is correct
3 Correct 517 ms 23696 KB Output is correct
4 Correct 551 ms 23848 KB Output is correct
5 Correct 544 ms 23828 KB Output is correct
6 Correct 511 ms 23844 KB Output is correct

Subtask #5
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 516 ms 23652 KB Output is correct - P = 5.000000
2 Correct 515 ms 23832 KB Output is correct - P = 5.000000
3 Correct 536 ms 24024 KB Output is correct - P = 5.000000
4 Correct 546 ms 24004 KB Output is correct - P = 5.000000
5 Correct 534 ms 23896 KB Output is correct - P = 4.366667
6 Correct 530 ms 23972 KB Output is correct - P = 4.158730
7 Correct 527 ms 24016 KB Output is correct - P = 4.093750