Submission #609556

#	Time	Username	Problem	Language	Result	Execution time	Memory
609556		Drew_	Match (CEOI16_match)	C++17	10 / 100	14 ms	21076 KiB

match

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define size(x) (int)x.size()

#define Int long long

using ll = long long;

const int MAX = 1e5 + 69;
const int ALPHA = 26;

int dp[MAX][ALPHA];
int main()
{
	ios :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	string s;
	cin >> s;

	vector<int> sk;
	for (char c : s)
	{
		if (!sk.empty() && sk.back() == c)
			sk.pop_back();
		else sk.pb(c);
	}

	if (!sk.empty())
	{
		cout << -1 << '\n';
		return 0;
	}

	memset(dp, 0, sizeof(dp));
	for (int i = 0; i < size(s); ++i)
	{
		for (int j = 0; j < ALPHA; ++j)
		{
			int lst = dp[i-1][s[i] - 'a'];

			if (s[i] == 'a' + j) dp[i][j] = i;
			else if (lst > 0) dp[i][j] = dp[lst - 1][j];
		}
	}

	const auto solve = [&](const auto &self, int l, int r) -> void
	{
		if (l > r)
			return;

		int tmp = dp[r][s[l] - 'a'];
		s[l] = '(', s[tmp] = ')';
		self(self, l+1, tmp-1);
		self(self, tmp+1, r);
	};
	solve(solve, 0, size(s)-1);

	cout << s << '\n';
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 63