Submission #53524

#	Time	Username	Problem	Language	Result	Execution time	Memory
53524		baactree	Match (CEOI16_match)	C++17	100 / 100	52 ms	41548 KiB

match

#include <bits/stdc++.h>
using namespace std;
struct node {
	node *ch[26], *par;
	vector<int> vec[26];
	char now;
	node(char now=0, node *par=0) :now(now), par(par) {
		memset(ch, 0, sizeof(ch));
	}
};
int n;
char str[100005];
node *s[100005];
vector<int> p[256][256];
void solve(int le, int ri) {
	if (le > ri)return;
	node *now = s[le - 1];
	auto it = upper_bound(now->vec[str[le] - 'a'].begin(), now->vec[str[le] - 'a'].end(), ri);
	int i = *(--it);
	str[le] = '(';
	str[i] = ')';
	solve(le + 1, i - 1);
	solve(i + 1, ri);
	return;
}
int main() {
	scanf("%s", str + 1);
	n = strlen(str + 1);
	stack<int> st;
	for (int i = 1; i <= n; i++) {
		if (!st.empty() && st.top() == str[i])st.pop();
		else st.push(str[i]);
	}
	if (!st.empty())return !printf("-1\n");
	node *root;
	root = new node;
	node *cur = root;
	s[0] = cur;
	for (int i = 1; i <= n; i++) {
		if (cur->now == str[i]) {
			cur = cur->par;
		}
		else {
			if (!cur->ch[str[i] - 'a'])
				cur->ch[str[i] - 'a'] = new node(str[i], cur);
			cur = cur->ch[str[i] - 'a'];
		}
		s[i] = cur;
		cur->vec[str[i] - 'a'].push_back(i);
	}
	solve(1, n);
	printf("%s\n", str + 1);
	return 0;
}

Compilation message (stderr)

match.cpp: In constructor 'node::node(char, node*)':
match.cpp:6:7: warning: 'node::now' will be initialized after [-Wreorder]
  char now;
       ^~~
match.cpp:4:17: warning:   'node* node::par' [-Wreorder]
  node *ch[26], *par;
                 ^~~
match.cpp:7:2: warning:   when initialized here [-Wreorder]
  node(char now=0, node *par=0) :now(now), par(par) {
  ^~~~
match.cpp: In function 'int main()':
match.cpp:27:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", str + 1);
  ~~~~~^~~~~~~~~~~~~~~

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