Submission #609543

#	Time	Username	Problem	Language	Result	Execution time	Memory
609543		Drew_	Match (CEOI16_match)	C++17	0 / 100	2073 ms	10452 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, -1, sizeof(dp));
	for (int i = 0; i < size(s); ++i)
	{
		for (int j = 0; j < 2; ++j)
		{
			if (s[i] == 'a' + j) dp[i][j] = i;
			else if (dp[i][s[i] - 'a'] > 0) dp[i][j] = dp[dp[i-1][s[i] - 'a'] - 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: 0 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 63