Submission #1071048

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071048		sleepntsheep	Ancient Machine (JOI21_ancient_machine)	C++17	38 / 100	102 ms	17920 KiB

Anna

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

namespace {
}

void Anna(int N, std::vector<char> S) {
	int freq[3] {}, ord[3] {};
	for (char c : S) ++freq[(int)(c - 'X')];

	int o[3] = {0, 1, 2};
	sort(o, o + 3, [&](int a, int b){ return freq[a] > freq[b]; });

	int j = 0;
	for (auto x : o) {
		Send(x >> 1);
		Send(x & 1);
		ord[x] = j++;
	}

	for (int i = 0; i < N; ++i) {
		int v = S[i] - 'X';
		switch (ord[v]) {
			case 0:
				Send(0);
				break;
			case 1:
				Send(1);
				Send(0);
				break;
			case 2:
				Send(1);
				Send(1);
				break;
		}
	}
}

Bruno

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

namespace {
	vector<int> decode(int N, vector<int> A) {
		int m1, m2, m3;
		vector<int> v;
		m1 = A[0] * 2 + A[1], m2 = A[2] * 2 + A[3], m3 = A[4] * 2 + A[5];
		for (int i = 6; i < (int)A.size(); )
			if (A[i] == 0)
				v.push_back(m1), ++i;
			else
				v.push_back((A[i + 1]) ? m3 : m2), ++i, ++i;
		return v;
	}
}  // namespace

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: 33 / 95