Submission #468892

#	Time	Username	Problem	Language	Result	Execution time	Memory
468892		superay	Ancient Machine (JOI21_ancient_machine)	C++17	100 / 100	69 ms	8580 KiB

Anna

#include "Anna.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
long long dp[64];
void Init() {
	dp[0] = 1, dp[1] = 2;
	for (int i = 2; i <= 63; i++) dp[i] = dp[i - 1] + dp[i - 2];
}
long long Encode(const vector<int> &a, int l, int r) {
	if (l > r) return 0;
	if (l == r) return a[l];
	if (a[l]) return dp[r - l] + Encode(a, l + 2, r);
	else return Encode(a, l + 1, r);
}
}
void Anna(int n, vector<char> s) {
	Init();
	vector<int> res;
	for (int i = 0; i < n; i++) if (s[i] == 'X') {
		res.push_back(1);
		res.push_back(0);
		for (int j = i + 1; j < n; j++) res.push_back(s[j] == 'Z' && (j == n - 1 || s[j + 1] != 'Z'));
		break;
	} else res.push_back(0);
	if ((int)res.size() == n) return;
	while (res.size() % 63) res.push_back(0);
	for (int i = 0; i < (int)res.size(); i += 63) {
		long long cur = Encode(res, i, i + 62);
		for (int j = 43; j >= 0; j--) Send(cur >> j & 1);
	}
}

Bruno

#include "Bruno.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
long long dp[64];
void Init() {
	dp[0] = 1, dp[1] = 2;
	for (int i = 2; i <= 63; i++) dp[i] = dp[i - 1] + dp[i - 2];
}
void Decode(vector<int> &a, long long cur, int l) {
	if (!l) return;
	if (l == 1) a.push_back(cur);
	else if (cur < dp[l - 1]) a.push_back(0), Decode(a, cur, l - 1);
	else a.push_back(1), a.push_back(0), Decode(a, cur - dp[l - 1], l - 2);
}
}
void Bruno(int n, int l, vector<int> a) {
	if (a.empty()) {
		for (int i = 0; i < n; i++) Remove(i);
		return;
	}
	Init();
	vector<int> res;
	for (int i = 0; i < l; i += 44) {
		long long cur = 0;
		for (int j = 0; j < 44; j++) if (a[i + j]) cur |= (1ll << (43 - j));
		Decode(res, cur, 63);
	}
	while ((int)res.size() > n + 1) res.pop_back();
	for (int i = 0; i < n; i++) if (res[i]) {
		res.erase(res.begin() + i + 1);
		for (int j = i - 1; j >= 0; j--) Remove(j);
		int lst = i;
		for (int j = i + 1; j < n; j++) if (res[j]) {
			for (int k = j - 1; k > lst; k--) Remove(k);
			Remove(j);
			lst = j;
		}
		for (int j = lst + 1; j < n; j++) Remove(j);
		Remove(i);
		break;
	}
}

• Subtask 1: 5 / 5
• Subtask 2: 95 / 95