Submission #800093

#	Time	Username	Problem	Language	Result	Execution time	Memory
800093		Sohsoh84	Ancient Machine (JOI21_ancient_machine)	C++17	100 / 100	50 ms	9292 KiB

Anna

#include "Anna.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

namespace {
	const int MAXN = 1e5;

	ll fib[MAXN];

	const int LEN_MAX = 50;
	const int BIT_MAX = 35;

	inline ll encode(vector<int> vec) {
		ll ans = 0;
		for (int i = 0; i < LEN_MAX; i++)
			if (vec[i])
				ans += fib[LEN_MAX - i - 1];

		return ans;
	}
}

void Anna(int N, vector<char> S) {
	fib[0] = 1, fib[1] = 2;
	for (int i = 2; i <= LEN_MAX; i++)
		fib[i] = fib[i - 1] + fib[i - 2];

	vector<int> ans = {0};
	for (int i = 1; i < N; i++) {
		ans.push_back(S[i - 1] == 'Z');
	}

	int ind = 0;
	while (S[ind] != 'X' && ind < N) ind++;
	if (ind == N) return;

	for (int i = 0; i <= ind; i++) ans[i] = 0;
	ans[ind] = 1;

	for (int i = N - 2; i >= 0; i--)
		if (ans[i] + ans[i + 1] == 2)
			ans[i] = 0;
	
	while (int(ans.size()) < MAXN) ans.push_back(0);

	vector<int> fans;
	for (int i = 0; i < int(ans.size()); i += LEN_MAX) {
		vector<int> tmp;
		for (int j = 0; j < LEN_MAX; j++)
			tmp.push_back(ans[i + j]);

		ll x = encode(tmp);
		for (int i = 0; i < BIT_MAX; i++)
			fans.push_back((x >> i & 1ll));
	}

	for (int e : fans)
		Send(e);
}

Bruno

#include "Bruno.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

namespace {
	const int MAXN = 1e5;
	const int MAX_LEN = 50;
	const int MAX_BIT = 35;

	ll fib[MAXN];

	inline vector<int> decode(ll x) {
		vector<int> ans;
		for (int i = 0; i < MAX_LEN; i++) {
			if (x >= fib[MAX_LEN - i - 1]) {
				ans.push_back(1);
				x -= fib[MAX_LEN - i - 1];
			} else {
				ans.push_back(0);
			}
		}

		return ans;
	}
}  // namespace

void Bruno(int N, int L, std::vector<int> TTA) {	
	if (!L) {
		for (int i = 0; i < N; i++)
			Remove(i);

		return;
	}

	fib[0] = 1, fib[1] = 2;
	for (int i = 2; i <= MAX_LEN; i++)
		fib[i] = fib[i - 1] + fib[i - 2];

	vector<int> TA;
	for (int i = 0; i < L; i += MAX_BIT) {
		ll x = 0;
		for (int j = 0; j < MAX_BIT; j++)
			if (TTA[i + j]) 
				x |= (1ll << j);

		vector<int> tmp = decode(x);
		for (int e : tmp)
			TA.push_back(e);
	}

	int ind = 0;
	vector<int> A(N);
	while (!TA[ind]) ind++;

	for (int i = 0; i < ind; i++)
		A[i] = 1;

	A[N - 1] = 1;
	for (int i = ind + 1; i < N; i++)
		A[i - 1] = TA[i];

	stack<int> st;
	bool flag = false;

	for (int i = 0; i < N; i++) {	
		if (A[i]) {
			while (st.size() > 1) {
				Remove(st.top());
				st.pop();
			}

			Remove(i);
		} else st.push(i);
	}

	while (!st.empty()) {
		Remove(st.top());
		st.pop();
	}
}

Compilation message (stderr)

Bruno.cpp: In function 'void Bruno(int, int, std::vector<int>)':
Bruno.cpp:66:7: warning: unused variable 'flag' [-Wunused-variable]
   66 |  bool flag = false;
      |       ^~~~

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