Submission #57184

#	Time	Username	Problem	Language	Result	Execution time	Memory
57184		Bruteforceman	Match (CEOI16_match)	C++11	100 / 100	44 ms	33428 KiB

match

#include <bits/stdc++.h>
using namespace std;
string s;
bool decide[100010];
int dp[26][100010];
int node[26][100010];
int par[100010];
char letter[100010];
int alpha[26][100010];
char ans[100010];

void solve(int l, int r) {
	if(l > r) {
		return ;
	}
	int opt = dp[s[l] - 'a'][r];
	if(opt <= l) {
		cout << -1 << endl;
		exit(0);
	}
	ans[l] = '(';
	ans[opt] = ')';
	solve(l + 1, opt - 1);
	solve(opt + 1, r);
}

int main(int argc, char const *argv[])
{
	ios_base :: sync_with_stdio (false);
	cin.tie();
	cin >> s;
	int n = s.size();
	letter[0] = '#';
	int cur = 0;
	int idx = 0;
	memset(node, -1, sizeof node);
	memset(alpha, -1, sizeof alpha);

	for(int i = 0; i < n; i++) {
		int c = s[i] - 'a';
		if(letter[cur] == s[i]) {
			cur = par[cur];
		} else {
			int nxt;
			if(node[c][cur] == -1) nxt = ++idx;
			else nxt = node[c][cur];
			node[c][cur] = nxt;
			par[nxt] = cur;
			letter[nxt] = s[i];
			cur = nxt;
		}
		alpha[c][cur] = i;
		for(int j = 0; j < 26; j++) {
			dp[j][i] = alpha[j][cur];
		}
	}
	solve(0, n-1);
	for(int i = 0; i < n; i++) {
		cout << ans[i];
	}
	cout << endl;
	return 0;
}

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