Submission #609559

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
609559	2022-07-27T17:17:32 Z	Drew_	Match (CEOI16_match)	C++17	100 / 100	12 ms	11480 KB

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));
	dp[0][s[0] - 'a'] = 0;
	for (int i = 1; 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.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	10452 KB	Output is correct
2	Correct	4 ms	10452 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct

Subtask #2

27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	10452 KB	Output is correct
2	Correct	4 ms	10452 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	5 ms	10452 KB	Output is correct
5	Correct	4 ms	10452 KB	Output is correct
6	Correct	4 ms	10452 KB	Output is correct
7	Correct	4 ms	10452 KB	Output is correct

Subtask #3

63.0 / 63.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	10452 KB	Output is correct
2	Correct	4 ms	10452 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	5 ms	10452 KB	Output is correct
5	Correct	4 ms	10452 KB	Output is correct
6	Correct	4 ms	10452 KB	Output is correct
7	Correct	4 ms	10452 KB	Output is correct
8	Correct	5 ms	10452 KB	Output is correct
9	Correct	5 ms	10452 KB	Output is correct
10	Correct	5 ms	10452 KB	Output is correct
11	Correct	5 ms	10580 KB	Output is correct
12	Correct	9 ms	11100 KB	Output is correct
13	Correct	8 ms	11096 KB	Output is correct
14	Correct	10 ms	11348 KB	Output is correct
15	Correct	10 ms	11424 KB	Output is correct
16	Correct	10 ms	11476 KB	Output is correct
17	Correct	11 ms	11480 KB	Output is correct
18	Correct	12 ms	11092 KB	Output is correct
19	Correct	12 ms	11280 KB	Output is correct
20	Correct	12 ms	11224 KB	Output is correct
21	Correct	12 ms	11476 KB	Output is correct