Submission #1071226

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071226		sleepntsheep	Ancient Machine (JOI21_ancient_machine)	C++17	40 / 100	126 ms	19404 KiB

Anna

#include "Anna.h"
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

namespace {
}

void Anna(int N, std::vector<char> S) {
	vector<int> v;
	for (int i = 0; i < N; ++i) 
		v.push_back(S[i] - 'X');
	while (v.size() < 100000) v.push_back(0);
	for (int i = 0; i < 100000; i += 5) {
		int x = v[i] + v[i + 1] * 3 + v[i + 2] * 3 * 3 + v[i + 3] * 3 * 3 * 3 + v[i + 4] * 3 * 3 * 3 * 3;
		for (int j = 0; j < 8; ++j) Send((x >> j) & 1);
	}
}

Bruno

#include "Bruno.h"
#include <set>
#include <vector>
#include <algorithm>
using namespace std;

namespace {
	vector<int> decode(int N, vector<int> A) {
		vector<int> v;
		for (int i = 0; i < (int)A.size(); i += 8) {
			int z = 0;
			for (int j = 0; j < 8; ++j) z |= (1 << j) * A[i + j];
			for (int j = 0; j < 5; ++j) v.push_back(z % 3), z /= 3;
		}
		v.resize(N);
		return v;
	}
}

void Bruno(int N, int L, vector<int> A) {
	auto v = decode(N, A);

	set<int> alv;
	vector<int> ded(N);
	for (int i = 0; i < N; ++i) alv.insert(i);

	vector<set<int> > oc(3);
	for (int i = 0; i < N; ++i)
		oc[v[i]].insert(i);

	if (oc[0].empty() or oc[2].empty() or *oc[0].begin() > *oc[2].rbegin()) {
		for (int i = 0; i < N; ++i) Remove(i);
		return;
	}

	int x0 = *oc[0].begin();
	int z0 = *oc[2].rbegin();

	auto REmove = [&](int i) { if (alv.count(i) == 0) return; alv.erase(i); oc[v[i]].erase(i); Remove(i); };
	auto REmove_range = [&](int i, int j) {
		for (auto it = alv.lower_bound(i); it != alv.end() && *it <= j; )
			Remove(*it), oc[v[*it]].erase(*it), it = alv.erase(it);
	};

	int at = x0;
	for (; at < z0 ;) {
		auto zi = oc[2].upper_bound(at);

		while (1) {
			auto yi = oc[1].lower_bound(*zi);
			if (yi == oc[1].begin() or *--yi < x0)
				break;
			auto xi = prev(oc[0].lower_bound(*yi));

			REmove_range(*xi + 1, *yi - 1);
			REmove_range(*yi + 1, *zi - 1);
			REmove(*yi);
			if (*xi != x0) REmove(*xi);
		}
		REmove_range(at + 1, *zi - 1);

		at = *zi;
	}

	for (int i = 0; i < N; ++i) REmove(i);

}

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