oj.uz

Submission #23987

# Submission time Handle Problem Language Result Execution time Memory
23987 2017-05-28T16:05:22 Z gs14004 Match (CEOI16_match) C++11
100 / 100
 13 ms 17864 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
const int mod = 1e9 + 7;
typedef pair<int, int> pi;

int n;
char str[100005], ans[100005];
int trie[100005][26], par[100005], pae[100005], idx[100005], piv;
vector<int> nv[100005];

bool solve(int s, int e){
	if(s == e) return true;
	auto l = lower_bound(nv[idx[s+1]].begin(), nv[idx[s+1]].end(), e);
	if(l == nv[idx[s+1]].begin()) return false;
	if(*--l > s){
		ans[s] = '(';
		ans[*l] = ')';
		return solve(s+1, *l) && solve(*l + 1, e);
	}
	else return false;
}

int main(){
	scanf("%s", str);
	n = strlen(str);
	int p = 0;
	for(int i=0; i<n; i++){
		if(p > 0 && pae[p] == str[i]){
			p = par[p];
			idx[i+1] = p;
			continue;
		}
		if(!trie[p][str[i] - 'a']) trie[p][str[i] - 'a'] = ++piv;
		int prv = p;
		p = trie[p][str[i] - 'a'];
		par[p] = prv;
		pae[p] = str[i];
		idx[i+1] = p;
	}
	for(int i=0; i<=n; i++) nv[idx[i]].push_back(i);
	if(p != 0 || n % 2 == 1 || !solve(0, n)){
		puts("-1");
		return 0;
	}
	puts(ans);
}

Compilation message

match.cpp: In function 'int main()':
match.cpp:26:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", str);
                  ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 15888 KB Output is correct
2 Correct 0 ms 15888 KB Output is correct
3 Correct 0 ms 15888 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 15888 KB Output is correct
2 Correct 0 ms 15888 KB Output is correct
3 Correct 0 ms 15888 KB Output is correct
4 Correct 0 ms 15888 KB Output is correct
5 Correct 0 ms 15888 KB Output is correct
6 Correct 0 ms 15888 KB Output is correct
7 Correct 0 ms 15888 KB Output is correct

Subtask #3
63.0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 15888 KB Output is correct
2 Correct 0 ms 15888 KB Output is correct
3 Correct 0 ms 15888 KB Output is correct
4 Correct 0 ms 15888 KB Output is correct
5 Correct 0 ms 15888 KB Output is correct
6 Correct 0 ms 15888 KB Output is correct
7 Correct 0 ms 15888 KB Output is correct
8 Correct 3 ms 16020 KB Output is correct
9 Correct 0 ms 16020 KB Output is correct
10 Correct 0 ms 16020 KB Output is correct
11 Correct 0 ms 16020 KB Output is correct
12 Correct 6 ms 17168 KB Output is correct
13 Correct 9 ms 17368 KB Output is correct
14 Correct 6 ms 17516 KB Output is correct
15 Correct 3 ms 17284 KB Output is correct
16 Correct 6 ms 17280 KB Output is correct
17 Correct 9 ms 17568 KB Output is correct
18 Correct 0 ms 16688 KB Output is correct
19 Correct 3 ms 17688 KB Output is correct
20 Correct 3 ms 17292 KB Output is correct
21 Correct 13 ms 17864 KB Output is correct