oj.uz

Submission #67338

# Submission time Handle Problem Language Result Execution time Memory
67338 2018-08-14T03:23:38 Z MatheusLealV Match (CEOI16_match) C++17
10 / 100
 6 ms 2980 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;

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

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

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2680 KB Output is correct
2 Correct 6 ms 2920 KB Output is correct
3 Correct 6 ms 2920 KB Output is correct
4 Incorrect 6 ms 2980 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2680 KB Output is correct
2 Correct 6 ms 2920 KB Output is correct
3 Correct 6 ms 2920 KB Output is correct
4 Incorrect 6 ms 2980 KB Output isn't correct
5 Halted 0 ms 0 KB -