oj.uz

Submission #67326

# Submission time Handle Problem Language Result Execution time Memory
67326 2018-08-14T02:42:41 Z MatheusLealV Match (CEOI16_match) C++17
37 / 100
 1471 ms 30152 KB 
#include <bits/stdc++.h>
#define N 2050
using namespace std;

int n, v[N], dp[N][N], prox[N][N];

string s;

vector<int> pos[N];

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[l][r] != -1) 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];

		if(!(l < p and p <= r)) 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;
	}

	resp[l] = '(';

	resp[prox[l][r]] = ')';

	getans(l + 1, prox[l][r] - 1), getans(prox[l][r] + 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);

	memset(dp, -1, sizeof dp);

	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 15 ms 16888 KB Output is correct
2 Correct 16 ms 17000 KB Output is correct
3 Correct 16 ms 17000 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16888 KB Output is correct
2 Correct 16 ms 17000 KB Output is correct
3 Correct 16 ms 17000 KB Output is correct
4 Correct 83 ms 21352 KB Output is correct
5 Correct 18 ms 21352 KB Output is correct
6 Correct 18 ms 21352 KB Output is correct
7 Correct 1471 ms 30152 KB Output is correct

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16888 KB Output is correct
2 Correct 16 ms 17000 KB Output is correct
3 Correct 16 ms 17000 KB Output is correct
4 Correct 83 ms 21352 KB Output is correct
5 Correct 18 ms 21352 KB Output is correct
6 Correct 18 ms 21352 KB Output is correct
7 Correct 1471 ms 30152 KB Output is correct
8 Runtime error 4 ms 30152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -