oj.uz

Submission #67332

# Submission time Handle Problem Language Result Execution time Memory
67332 2018-08-14T02:59:11 Z MatheusLealV Match (CEOI16_match) C++17
37 / 100
 2000 ms 35308 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;

	if(dp.find({l, r}) != dp.end()) return dp[{l, r}];

	prox[{l, r}] = -1;

	int esq = lower_bound(pos[v[l]].begin(), pos[v[l]].end(), l) - pos[v[l]].begin();

	int dir = min((int)(upper_bound(pos[v[l]].begin(), pos[v[l]].end(), r) - pos[v[l]].begin()), (int)pos[v[l]].size() - 1);

	for(int j = dir; j >= esq; j--)
	{
		int p = pos[v[l]][j], nop = 0;

		if(!(l < p and p <= r)) continue;

		for(int t = 0; t < 30; t++)
		{
			if( (qtd[p - 1][t] - qtd[l][t])%2 or (qtd[r][t] - qtd[p][t])%2)
			{
				nop = 1;

				break;
			}
		}

		if(nop) continue;

		if(solve(l + 1, p - 1) and solve(p + 1, r))
		{
			prox[{l, r}] = p;

			break;
		}
	}

	if(prox[{l, r}] == - 1) return dp[{l, r}] = 0;

	return dp[{l, r}] = 1;
}

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 5 ms 2680 KB Output is correct
2 Correct 5 ms 2800 KB Output is correct
3 Correct 4 ms 2800 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2680 KB Output is correct
2 Correct 5 ms 2800 KB Output is correct
3 Correct 4 ms 2800 KB Output is correct
4 Correct 9 ms 3148 KB Output is correct
5 Correct 4 ms 3148 KB Output is correct
6 Correct 5 ms 3204 KB Output is correct
7 Correct 359 ms 8636 KB Output is correct

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2680 KB Output is correct
2 Correct 5 ms 2800 KB Output is correct
3 Correct 4 ms 2800 KB Output is correct
4 Correct 9 ms 3148 KB Output is correct
5 Correct 4 ms 3148 KB Output is correct
6 Correct 5 ms 3204 KB Output is correct
7 Correct 359 ms 8636 KB Output is correct
8 Correct 97 ms 8636 KB Output is correct
9 Correct 555 ms 9260 KB Output is correct
10 Correct 10 ms 9260 KB Output is correct
11 Correct 12 ms 9260 KB Output is correct
12 Correct 79 ms 16696 KB Output is correct
13 Correct 77 ms 17880 KB Output is correct
14 Correct 219 ms 19352 KB Output is correct
15 Execution timed out 2062 ms 35308 KB Time limit exceeded
16 Halted 0 ms 0 KB -