oj.uz

Submission #103664

# Submission time Handle Problem Language Result Execution time Memory
103664 2019-04-01T22:29:39 Z Anai Match (CEOI16_match) C++14
10 / 100
 4 ms 640 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 void solve(int l, int r) {
	if (l > r)
		return;
	int match = dp[str[l] - 'a'][r];

	if (!match)
		throw -1;

	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);

	vector<int> stk;
	stk.reserve(n);
	for (int ch = 'a'; ch <= 'z'; ++ch) {
		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; } }

	try {
		solve(1, n); }
	catch (int e) {
		cout << "-1\n";
		return 0; }

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

	return 0; }

Compilation message

match.cpp: In function 'int main()':
match.cpp:41:8: warning: unused variable 'flag' [-Wunused-variable]
   bool flag = false;
        ^~~~
match.cpp:55: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 4 ms 512 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 4 ms 512 KB Output is correct
4 Incorrect 4 ms 640 KB Output isn't correct
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 4 ms 512 KB Output is correct
4 Incorrect 4 ms 640 KB Output isn't correct
5 Halted 0 ms 0 KB -