oj.uz

Submission #53524

# Submission time Handle Problem Language Result Execution time Memory
53524 2018-06-30T07:19:32 Z baactree Match (CEOI16_match) C++17
100 / 100
 52 ms 41548 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1784 KB Output is correct
2 Correct 3 ms 1896 KB Output is correct
3 Correct 3 ms 1948 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1784 KB Output is correct
2 Correct 3 ms 1896 KB Output is correct
3 Correct 3 ms 1948 KB Output is correct
4 Correct 3 ms 2204 KB Output is correct
5 Correct 3 ms 2388 KB Output is correct
6 Correct 3 ms 2388 KB Output is correct
7 Correct 3 ms 2388 KB Output is correct

Subtask #3
63.0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1784 KB Output is correct
2 Correct 3 ms 1896 KB Output is correct
3 Correct 3 ms 1948 KB Output is correct
4 Correct 3 ms 2204 KB Output is correct
5 Correct 3 ms 2388 KB Output is correct
6 Correct 3 ms 2388 KB Output is correct
7 Correct 3 ms 2388 KB Output is correct
8 Correct 5 ms 3904 KB Output is correct
9 Correct 6 ms 4420 KB Output is correct
10 Correct 6 ms 5200 KB Output is correct
11 Correct 7 ms 5260 KB Output is correct
12 Correct 44 ms 29196 KB Output is correct
13 Correct 34 ms 31632 KB Output is correct
14 Correct 51 ms 33124 KB Output is correct
15 Correct 9 ms 33124 KB Output is correct
16 Correct 9 ms 33124 KB Output is correct
17 Correct 27 ms 33124 KB Output is correct
18 Correct 9 ms 33124 KB Output is correct
19 Correct 49 ms 41548 KB Output is correct
20 Correct 33 ms 41548 KB Output is correct
21 Correct 52 ms 41548 KB Output is correct