oj.uz

Submission #67340

# Submission time Handle Problem Language Result Execution time Memory
67340 2018-08-14T03:31:13 Z MatheusLealV Match (CEOI16_match) C++17
37 / 100
 2000 ms 39164 KB 
#include <bits/stdc++.h>
#define N 100050
#define f first
#define s second
using namespace std;
typedef pair<int, int> pii;

int n, v[N];

int qtd[N][30];

string s;

vector<int> pos[N];

char resp[N];

int solve(int l, int r)
{
	if(r < l) return 1;

	if(r - l == 1)
	{
		resp[l] = '(', resp[r] = ')';

		return (v[l] == v[r]);
	}

	if(l == r) return 0;

	stack<int> open;

	for(int j = r; j > l; j--)
	{
		if(!open.empty())
		{
			int t = open.top();

			if(t == v[j]) open.pop();

			else open.push(v[j]);
		}

		else
		{
			if(v[l] == v[j])
			{
				resp[l] = '(', resp[j] = ')';

				return (solve(l + 1, j - 1) and solve(j + 1, r));
			}

			open.push(v[j]);
		}
	}

	return 0;
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin>>s;

	n = s.size();

	for(int i = 1; i <= n; i++) v[i] = s[i - 1] - 'a';

	for(int i = 1; i <= n; i++) pos[v[i]].push_back(i);

	for(int i = 0; i < 30; i++)
		for(int j = 1; j <= n; j++) qtd[j][i] = qtd[j - 1][i] + (v[j] == i);

	if(solve(1, n))
	{
		for(int i = 1; i<= n; i++) cout<<resp[i];

		cout<<"\n";
	}

	else cout<<"-1\n";
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2684 KB Output is correct
2 Correct 4 ms 2792 KB Output is correct
3 Correct 5 ms 2828 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2684 KB Output is correct
2 Correct 4 ms 2792 KB Output is correct
3 Correct 5 ms 2828 KB Output is correct
4 Correct 5 ms 3116 KB Output is correct
5 Correct 5 ms 3116 KB Output is correct
6 Correct 5 ms 3576 KB Output is correct
7 Correct 5 ms 3576 KB Output is correct

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2684 KB Output is correct
2 Correct 4 ms 2792 KB Output is correct
3 Correct 5 ms 2828 KB Output is correct
4 Correct 5 ms 3116 KB Output is correct
5 Correct 5 ms 3116 KB Output is correct
6 Correct 5 ms 3576 KB Output is correct
7 Correct 5 ms 3576 KB Output is correct
8 Correct 7 ms 3876 KB Output is correct
9 Correct 18 ms 5412 KB Output is correct
10 Correct 10 ms 5412 KB Output is correct
11 Correct 10 ms 6260 KB Output is correct
12 Correct 150 ms 23836 KB Output is correct
13 Correct 95 ms 25476 KB Output is correct
14 Correct 774 ms 36968 KB Output is correct
15 Correct 54 ms 37632 KB Output is correct
16 Correct 53 ms 37640 KB Output is correct
17 Correct 137 ms 39164 KB Output is correct
18 Correct 66 ms 39164 KB Output is correct
19 Correct 1287 ms 39164 KB Output is correct
20 Correct 558 ms 39164 KB Output is correct
21 Execution timed out 2058 ms 39164 KB Time limit exceeded