Submission #103663

#	Time	Username	Problem	Language	Result	Execution time	Memory
103663		Anai	Match (CEOI16_match)	C++14	10 / 100	2055 ms	512 KiB

match

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

const int N = 1e5 + 5, S = 26;


char str[N], ant[N];
int dp[S][N];

int n;

static bool check() {
	vector<char> stk;
	for (int i = 1; i <= n; ++i)
		if (!stk.empty() && stk.back() == str[i])
			stk.pop_back();
		else
			stk.push_back(str[i]);
	return stk.empty(); }

static void solve(int l, int r) {
	if (l > r)
		return;
	int match = dp[str[l] - 'a'][r];

	ant[l] = '(';
	ant[match] = ')';

	solve(l + 1, match - 1);
	solve(match + 1, r); }

int main() {
#ifdef HOME
	freopen("match.in", "r", stdin);
	freopen("match.out", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> (str + 1);
	n = strlen(str + 1);

	if (!check()) {
		cout << "-1\n";
		return 0; }

	for (int ch = 'a'; ch <= 'z'; ++ch) {
		vector<int> stk;
		int idx = ch - 'a';
		bool flag = false;

		for (int lst, i = 1; i <= n; ++i) {
			if (str[i] == ch) {
				dp[idx][i] = i;
				stk.clear();
				lst = i;
				continue; }

			if (!stk.empty() && str[stk.back()] == str[i])
				stk.pop_back();
			else
				stk.push_back(i);
			if (stk.empty())
				dp[idx][i] = lst; } }

	solve(1, n);

	cout << (ant + 1) << endl;

	return 0; }

Compilation message (stderr)

match.cpp: In function 'int main()':
match.cpp:50:8: warning: unused variable 'flag' [-Wunused-variable]
   bool flag = false;
        ^~~~
match.cpp:64:16: warning: 'lst' may be used uninitialized in this function [-Wmaybe-uninitialized]
     dp[idx][i] = lst; } }
     ~~~~~~~~~~~^~~~~

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