Submission #67344

#	Time	Username	Problem	Language	Result	Execution time	Memory
67344		MatheusLealV	괄호 문자열 (CEOI16_match)	C++17	100 / 100	1878 ms	2604 KiB

match

#include <bits/stdc++.h>
#define N 100050
#define f first
#define s second
using namespace std;
int n, v[N];

string s;

char resp[N], open[N];

bool 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;

	int id = 0;

	for(int j = r; j > l; j--)
	{
		if(id)
		{
			int t = open[id];

			if(t == v[j]) id--;

			else
			{
				id++;

				open[id] = v[j];
			}
		}

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

				bool A = solve(l + 1, j - 1);

				if(A) return solve(j + 1, r);

				else return 0;
			}

			++id;

			open[id] = (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';

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

		cout<<"\n";
	}

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

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 63 / 63