Submission #1246520

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246520		flappybird	Message (IOI24_message)	C++20	100 / 100	1799 ms	860 KiB

message

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

typedef long long ll;

int B[40][40];

int mxval[5];
int val[5];
int lv[40];
int isval[40];

void init() {
	int i, j;
	for (i = 0; i <= 32; i++) {
		for (j = 0; j <= i; j++) {
			if (i == j || i == 0 || j == 0) B[i][j] = 1;
			else B[i][j] = B[i - 1][j] + B[i - 1][j - 1];
		}
	}
}

void init_A() {
	int i;
	init();
	memset(mxval, 0, sizeof(mxval));
	memset(lv, 0, sizeof(lv));
	for (i = 0; i < 4; i++) mxval[i] = B[1 << (4 - i)][1 << (3 - i)];
}

void init_B() {
	int i;
	init();
	memset(lv, 0, sizeof(isval));
}

void send_message(std::vector<bool> M, std::vector<bool> C) {
	init_A();

	M.push_back(1);
	M.resize(1025);
	int i;
	int lastbit = 0;
	for (i = 0; i < 23; i++) if (M[M.size() - 23 + i]) lastbit |= (1 << i);
	M.resize(M.size() - 23);

	for (i = 3; i >= 0; i--) {
		val[i] = lastbit % mxval[i];
		lastbit /= mxval[i];
	}
	assert(lastbit == 0);

	int ptr = 0;
	auto getnext = [&]() {
		if (ptr >= M.size()) return false;
		return (bool)M[ptr++];
		};

	int d;
	//for (i = 0; i < 31; i++) if (!C[i]) lv[i] = 0;
	for (d = 0; d < 4; d++) {
		vector<bool> v;
		int N = 1 << (3 - d); //len: 2N, choose N indexes
		for (i = 0; i < N; i++) v.push_back(0);
		for (i = 0; i < N; i++) v.push_back(1);
		for (i = 0; i < val[d]; i++) next_permutation(v.begin(), v.end());
		int p = 0;
		vector<bool> sv(31);
		for (i = 0; i < 31; i++) if (!C[i]) {
			if (lv[i] == d) sv[i] = v[p++];
			else sv[i] = getnext();
		}
		auto res = send_packet(sv);
		int cnt[2] = { 0, 0 };
		for (i = 0; i < 31; i++) if (lv[i] == d && C[i]) cnt[res[i]]++;
		int c = 0;
		if (cnt[0] > cnt[1]) c = 1;
		for (i = 0; i < 31; i++) if (lv[i] == d && res[i] == c) lv[i]++;
	}
	int key = 0;
	for (i = 0; i < 31; i++) {
		if (lv[i] == 4) {
			key = i;
			break;
		}
	}

	for (d = 0; d < 4; d++) val[d] = 0;

	for (d = 0; d < 4; d++) {
		int t, f;
		t = f = 0;
		vector<int> v;
		for (i = 0; i < 31; i++) if (lv[i] == d) {
			v.push_back(C[i]);
			if (C[i]) f++;
			else t++;
		}
		mxval[d] = B[t + f][t];
		while (prev_permutation(v.begin(), v.end())) val[d]++;
	}

	int sum = 0;
	for (i = 0; i < 4; i++) {
		sum *= mxval[i];
		sum += val[i];
	}

	int rem = 24;

	while (ptr < M.size()) {
		vector<bool> sv(31);
		for (i = 0; i < 31; i++) {
			if (C[i]) continue;
			if (i == key && rem) {
				rem--;
				sv[i] = sum & 1;
				sum >>= 1;
			}
			else sv[i] = getnext();
		}
		send_packet(sv);
	}
}

std::vector<bool> receive_message(std::vector<std::vector<bool>> R) {
	init_B();
	int d, i;
	for (d = 0; d < 4; d++) {
		int cnt[2] = { 0, 0 };
		for (i = 0; i < 31; i++) if (lv[i] == d) cnt[R[d][i]]++;
		int c = 0;
		if (cnt[0] > cnt[1]) c = 1;
		for (i = 0; i < 31; i++) if (lv[i] == d && R[d][i] == c) lv[i]++;
	}
	int key = 0;
	int lcnt[4] = { 0, 0, 0, 0 };
	for (i = 0; i < 31; i++) {
		if (lv[i] == 4) key = i;
		else lcnt[lv[i]]++;
	}
	for (i = 0; i < 4; i++) mxval[i] = B[lcnt[i]][1 << (3 - i)];
	int mul = 0;
	for (i = 0; i < 24; i++) if (R[i + 4][key]) mul |= (1 << i);
	for (i = 3; i >= 0; i--) {
		val[i] = mul % mxval[i];
		mul /= mxval[i];
	}
	isval[key] = 1;
	for (d = 0; d < 4; d++) {
		vector<int> v(lcnt[d], 1);
		for (i = 0; i < (1 << 3 - d); i++) v[i] = 0;
		for (i = 0; i < val[d]; i++) next_permutation(v.begin(), v.end());
		int p = 0;
		for (i = 0; i < 31; i++) if (lv[i] == d) isval[i] = 1 - v[p++];
	}
	vector<bool> ans;
	for (d = 1; d < 4; d++) {
		for (i = 0; i < 31; i++) {
			if (isval[i] && lv[i] < d) {
				ans.push_back(R[d][i]);
			}
		}
	}
	for (d = 4; d < R.size(); d++) {
		for (i = 0; i < 31; i++) if (isval[i]) {
			if (i == key && d < 28) continue;
			ans.push_back(R[d][i]);
		}
	}
	assert(ans.size() >= 1002);
	ans.resize(1002);
	for (i = 0; i < 4; i++) mxval[i] = B[1 << (4 - i)][1 << (3 - i)];
	for (d = 0; d < 4; d++) {
		vector<int> v;
		for (i = 0; i < 31; i++) if (isval[i] && lv[i] >= d) v.push_back(R[d][i]);
		val[d] = 0;
		while (prev_permutation(v.begin(), v.end())) val[d]++;
	}

	int lastbit = 0;
	for (i = 0; i < 4; i++) {
		lastbit *= mxval[i];
		lastbit += val[i];
	}

	for (i = 0; i < 23; i++) {
		ans.push_back(lastbit & 1);
		lastbit >>= 1;
	}

	while (!ans.back()) ans.pop_back();
	ans.pop_back();

	return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 90 / 90