Submission #666503

#	Time	Username	Problem	Language	Result	Execution time	Memory
666503		rainboy	Ancient Machine (JOI21_ancient_machine)	C++17	100 / 100	66 ms	7688 KiB

Anna

#include "Anna.h"
#include <cassert>
#include <vector>

using namespace std;

typedef vector<char> str;

namespace A {
	const int N = 100001, K = 63, L = 44, M = 70000;
	long long ff[K + 1];
	void init() {
		ff[0] = 1, ff[1] = 2;
		for (int i = 2; i <= K; i++)
			ff[i] = ff[i - 1] + ff[i - 2];
		assert(1LL << L >= ff[K] && (N + K - 1) / K * L <= M);
	}
}

void encode(str aa, int n) {
	for (int i = 0; i < n; i += A::K) {
		long long x = 0;
		for (int j = 0; j < A::K && i + j < n; j++)
			if (aa[i + j] == 1)
				x += A::ff[j];
		for (int l = 0; l < A::L; l++)
			Send(x >> l & 1);
	}
}

void Anna(int n, str cc) {
	A::init();
	int ix = 0;
	while (ix < n && cc[ix] != 'X')
		ix++;
	int iz = n - 1;
	while (iz >= 0 && cc[iz] != 'Z')
		iz--;
	str aa(n + 1, 0);
	if (ix < iz) {
		aa[ix] = 1;
		for (int i = ix + 1; i < iz; i++)
			if (cc[i] == 'Z' && cc[i + 1] == 'Y')
				aa[i + 1] = 1;
		aa[iz + 1] = 1;
	}
	encode(aa, n + 1);
}

Bruno

#include "Bruno.h"
#include <cassert>
#include <vector>

using namespace std;

typedef vector<int> vi;

namespace B {
	const int N = 100001, K = 63, L = 44, M = 70000;
	long long ff[K + 1];
	void init() {
		ff[0] = 1, ff[1] = 2;
		for (int i = 2; i <= K; i++)
			ff[i] = ff[i - 1] + ff[i - 2];
		assert(1LL << L >= ff[K] && (N + K - 1) / K * L <= M);
	}
}

vi decode(vi aa, int n) {
	vi bb(n / B::L * B::K, 0);
	for (int i = 0; i < n; i += B::L) {
		long long x = 0;
		for (int l = 0; l < B::L; l++)
			if (aa[i + l] == 1)
				x |= 1LL << l;
		int j = B::K - 1;
		while (j >= 0)
			if (x >= B::ff[j])
				x -= B::ff[j], bb[i / B::L * B::K + j] = 1, j -= 2;
			else
				j--;
	}
	return bb;
}

void Bruno(int n, int l, vi aa) {
	B::init();
	aa = decode(aa, l);
	int ix = 0;
	while (ix < n && aa[ix] == 0)
		ix++;
	if (ix == n)
		for (int i = 0; i < n; i++)
			Remove(i);
	else {
		for (int i = ix + 1; i < n; i++)
			aa[i] = aa[i + 1];
		int iz = n - 1;
		while (iz >= 0 && aa[iz] == 0)
			iz--;
		for (int h = ix, i = ix + 1; i <= iz; i++)
			if (aa[i] == 1) {
				for (int j = i - 1; j > h; j--)
					Remove(j);
				h = i + 1;
			}
		for (int i = ix + 1; i <= iz; i++)
			if (aa[i] == 1) {
				Remove(i);
				if (i < iz)
					Remove(i + 1);
			}
		for (int i = ix; i >= 0; i--)
			Remove(i);
		for (int i = iz + 1; i < n; i++)
			Remove(i);
	}
}

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