Submission #547987

#	Time	Username	Problem	Language	Result	Execution time	Memory
547987		SamNguyen	Ancient Machine (JOI21_ancient_machine)	C++17	5 / 100	573 ms	6852 KiB

Anna

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

void Anna(int N, vector<char> S) {
	for (char c : S) {
		if (c == 'X') Send(0), Send(0);
		if (c == 'Y') Send(0), Send(1);
		if (c == 'Z') Send(1), Send(0);
	}

	cerr << "Anna done." << endl;
}

Bruno

#include "Bruno.h"
#include <vector>
#include <string>
#include <cstring>
#include <iostream>
#include <bitset>
using namespace std;

namespace {
	inline bool maximise(int &x, int y) {
		if (x < y) { x = y; return true; }
		return false;
	}

	int dp[1 << 18], par[1 << 18];
}

void Bruno(int N, int L, std::vector<int> A) {
	cerr << "Code: ";
	for (int e : A) cerr << e << " ";
	cerr << endl;

	string s = "";
	for (int i = 0; i < L; i += 2) {
		int x = A[i] << 1 | A[i + 1];
		char c = (x == 0) ? 'X' : (x == 1) ? 'Y' : 'Z';
		s.push_back(c);
	}

	cerr << "s = " << s << endl;

	const int FULL = (1 << N) - 1;

	memset(dp, -0x2f, sizeof dp);
	memset(par, 0, sizeof par);
	dp[0] = 0;

	for (int mask = 1; mask <= FULL; mask++) {
		vector<int> elem;
		for (int i = 0; i < N; i++) if (mask & (1 << i))
			elem.push_back(i);

		for (int j = 0; j < (int)elem.size(); j++) {
			int i = elem[j];
			int prv_mask = mask ^ (1 << i);

			int delta = 0;
			if (s[i] == 'Y')
			if (j - 1 >= 0 and s[elem[j - 1]] == 'X')
			if (j + 1 < (int)elem.size() and s[elem[j + 1]] == 'Z')
				delta = 1;

			if (maximise(dp[mask], dp[prv_mask] + delta))
				par[mask] = prv_mask;
		}
	}

	int mask = FULL;
	while (mask > 0) {
		int tmp = mask ^ par[mask];
		int i = 0;
		while ((1 << i) != tmp) i++;

		Remove(i);
		mask = par[mask];
	}
}

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