oj.uz

Submission #67339

# Submission time Handle Problem Language Result Execution time Memory
67339 2018-08-14T03:29:50 Z MatheusLealV Match (CEOI16_match) C++17
37 / 100
 2000 ms 42124 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];

map<pii, int> dp, prox;

char resp[N];

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

	if(r - l == 1) 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])
			{
				prox[{l, r}] = j;

				//cout<<"L "<<l<<" "<<j<<"\n";

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

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

	return 0;
}

void getans(int l, int r)
{
	if(r < l) return;

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

		return;
	}

	int p = prox[{l, r}];

	resp[l] = '(';

	resp[p] = ')';

	getans(l + 1, p - 1), getans(p + 1, r);
}

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))
	{
		getans(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 4 ms 2680 KB Output is correct
2 Correct 4 ms 2792 KB Output is correct
3 Correct 4 ms 2868 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2792 KB Output is correct
3 Correct 4 ms 2868 KB Output is correct
4 Correct 5 ms 3068 KB Output is correct
5 Correct 4 ms 3068 KB Output is correct
6 Correct 5 ms 3628 KB Output is correct
7 Correct 5 ms 3628 KB Output is correct

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2792 KB Output is correct
3 Correct 4 ms 2868 KB Output is correct
4 Correct 5 ms 3068 KB Output is correct
5 Correct 4 ms 3068 KB Output is correct
6 Correct 5 ms 3628 KB Output is correct
7 Correct 5 ms 3628 KB Output is correct
8 Correct 8 ms 4076 KB Output is correct
9 Correct 18 ms 5612 KB Output is correct
10 Correct 11 ms 5612 KB Output is correct
11 Correct 11 ms 6500 KB Output is correct
12 Correct 159 ms 25236 KB Output is correct
13 Correct 112 ms 27104 KB Output is correct
14 Correct 760 ms 39244 KB Output is correct
15 Correct 87 ms 40796 KB Output is correct
16 Correct 75 ms 40796 KB Output is correct
17 Correct 172 ms 42124 KB Output is correct
18 Correct 90 ms 42124 KB Output is correct
19 Correct 1240 ms 42124 KB Output is correct
20 Correct 523 ms 42124 KB Output is correct
21 Execution timed out 2080 ms 42124 KB Time limit exceeded