oj.uz

Submission #609545

# Submission time Handle Problem Language Result Execution time Memory
609545 2022-07-27T17:05:47 Z Drew_ Match (CEOI16_match) C++17
10 / 100
 15 ms 21100 KB 
#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 < ALPHA; ++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
10.0 / 10.0

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

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10452 KB Output is correct
2 Correct 6 ms 10452 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Runtime error 15 ms 21100 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10452 KB Output is correct
2 Correct 6 ms 10452 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Runtime error 15 ms 21100 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -