Submission #1244393

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244393		erray	Hieroglyphs (IOI24_hieroglyphs)	C++20	0 / 100	1093 ms	13128 KiB

hieroglyphs

#include <bits/stdc++.h>
#include <vector>
#include "hieroglyphs.h"
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;
};

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

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

vector<int> find_boundaries(vector<int> a, vector<int> b) {
	int n = int(a.size()), m = int(b.size());
	vector<int> occ_diff(MAX);
	for (auto x : a) occ_diff[x]++;
	for (auto x : b) occ_diff[x]--;
	vector<bool> mine(MAX);
	for (int i = 0; i < MAX; ++i) {
		if (occ_diff[i] <= 0) mine[i] = true;
	}
	vector<vector<int>> pos(MAX);
	for (int i = 0; i < m; ++i) pos[b[i]].push_back(i);
	vector<int> first_sub(n, m + 1);
	for (int i = 0; i < n; ++i) {
		if(!mine[a[i]]) continue;
		auto& v = pos[a[i]];
		int len = int(v.size());
		int x = m + 1;
		int j = i - 1;
		for (j = i - 1; j >= 0; --j) {
			cmin(x, first_sub[j]);
			if (a[i] == a[j]) break;
		}
		if (j == -1) x = -1;
		int next_ind = int(lower_bound(v.begin(), v.end(), x + 1) - v.begin());
		assert(next_ind < len);
		first_sub[i] = v[next_ind];				
	}
	vector<bool> after_me(MAX);
	vector<int> previous_to(n, m + 1);
	for (int i = n - 1; i >= 0; --i) {
		if (!mine[a[i]]) after_me[a[i]] = true;
		else {
			int j = first_sub[i];
			while (j < m && !(after_me[b[j]] && pos[b[j]].back() == j)) ++j;
			previous_to[i] = j;
		}
	}
	return previous_to;
}

std::vector<int> ucs(std::vector<int> A, std::vector<int> B) {
	int N = int(A.size()), M = int(B.size());
	vector<int> occ_A(MAX), occ_B(MAX);
	debug(A, B);
	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]);
	}
	auto previous_to_A = find_boundaries(A, B);
	auto previous_to_B = find_boundaries(B, A);

	debug(previous_to_A);
	debug(previous_to_B);
	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] && previous_to_A[i] > j && previous_to_B[j] > i && 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;
			}
		}
	}
	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