oj.uz

답안 #547987

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
547987 2022-04-12T07:32:02 Z SamNguyen Ancient Machine (JOI21_ancient_machine) C++17
5 / 100
 573 ms 6852 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 = 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.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 2564 KB Output is correct
2 Correct 58 ms 2656 KB Output is correct
3 Correct 60 ms 2656 KB Output is correct
4 Correct 61 ms 2568 KB Output is correct
5 Correct 65 ms 2652 KB Output is correct
6 Correct 62 ms 2560 KB Output is correct
7 Correct 2 ms 2568 KB Output is correct
8 Correct 2 ms 2568 KB Output is correct
9 Correct 56 ms 2572 KB Output is correct
10 Correct 56 ms 2568 KB Output is correct
11 Correct 55 ms 2584 KB Output is correct

Subtask #2
0 / 95.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 573 ms 6852 KB Wrong Answer [5]
2 Halted 0 ms 0 KB -