Submission #1243538

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243538		erray	Hieroglyphs (IOI24_hieroglyphs)	C++20	0 / 100	991 ms	2162688 KiB

hieroglyphs

#include "hieroglyphs.h"
#include <bits/stdc++.h>
#include <vector>

using namespace std;

#ifdef DEBUG
	#include "debug.h"
#else 
	#define debug(...) void(37)
#endif

template<typename T> bool cmax(T& x, T y) { 
	if (y > x) {
		x = y;
		return true;
	}
	return false;
};

constexpr int MAX = int(2e5) + 1;

std::vector<int> ucs(std::vector<int> A, std::vector<int> B) {
	int N = int(A.size()), M = int(B.size());
	vector<vector<int>> longest(N + 1, vector<int>(M + 1));
	vector<vector<int>> from(N + 1, vector<int>(M + 1, -1));
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			if (A[i] == B[j] && cmax(longest[i + 1][j + 1], longest[i][j] + 1)) {
				from[i + 1][j + 1] = 3;
			}
			if (cmax(longest[i + 1][j], longest[i][j])) {
				from[i + 1][j] = 1;
			}
			if (cmax(longest[i][j + 1], longest[i][j])) {
				from[i][j + 1] = 2;
			}
		}
	}
	vector<int> occ_A(MAX), occ_B(MAX);
	for (auto x : A) occ_A[x]++;
	for (auto x : B) occ_B[x]++;
	int req_len = 0;
	for (int i = 0; i < MAX; ++i) {
		req_len += min(occ_A[i], occ_B[i]);
	}
	if (req_len != longest[N][M]) {
		return {-1};
	} else {
		vector<int> ans;
		{
			int i = N, j = M;
			while (int(ans.size()) < req_len) {
				int to = from[i][j];
				i -= to & 1;
				j -= (to >> 1) & 1;
				if (to == 3) {
					ans.push_back(A[i]);
				}
			}
		}
		reverse(ans.begin(), ans.end());
		return ans;
	}
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 3
• Subtask 2: 0 / 15
• Subtask 3: 0 / 10
• Subtask 4: 0 / 16
• Subtask 5: 0 / 14
• Subtask 6: 0 / 42