oj.uz

Submission #547986

# Submission time Handle Problem Language Result Execution time Memory
547986 2022-04-12T07:24:26 Z SamNguyen Ancient Machine (JOI21_ancient_machine) C++17
0 / 100
 537 ms 7116 KB 
#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;
}
#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 = s[i] == 'Y' 
				    and j > 0 and s[elem[j - 1]] == 'X' 
					and j + 1 < (int)elem.size() and s[elem[j + 1]] == 'Y';

			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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 56 ms 2564 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 95.0

# Verdict Execution time Memory Grader output
1 Incorrect 537 ms 7116 KB Wrong Answer [5]
2 Halted 0 ms 0 KB -