oj.uz

Submission #103663

# Submission time Handle Problem Language Result Execution time Memory
103663 2019-04-01T22:27:57 Z Anai Match (CEOI16_match) C++14
10 / 100
 2000 ms 512 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 3 ms 384 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Execution timed out 2055 ms 512 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Execution timed out 2055 ms 512 KB Time limit exceeded
5 Halted 0 ms 0 KB -