oj.uz

답안 #67332

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
67332 2018-08-14T02:59:11 Z MatheusLealV 괄호 문자열 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -