oj.uz

Submission #114704

# Submission time Handle Problem Language Result Execution time Memory
114704 2019-06-02T11:44:59 Z 구사과(#2864) Match (CEOI16_match) C++14
100 / 100
 18 ms 9984 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:7: 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 4 ms 2688 KB Output is correct
2 Correct 4 ms 2688 KB Output is correct
3 Correct 4 ms 2688 KB Output is correct

Subtask #2
27.0 / 27.0

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

Subtask #3
63.0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Correct 4 ms 2688 KB Output is correct
3 Correct 4 ms 2688 KB Output is correct
4 Correct 4 ms 2816 KB Output is correct
5 Correct 4 ms 2816 KB Output is correct
6 Correct 4 ms 2816 KB Output is correct
7 Correct 4 ms 2816 KB Output is correct
8 Correct 5 ms 3072 KB Output is correct
9 Correct 5 ms 3200 KB Output is correct
10 Correct 5 ms 3328 KB Output is correct
11 Correct 5 ms 3328 KB Output is correct
12 Correct 11 ms 7808 KB Output is correct
13 Correct 12 ms 8192 KB Output is correct
14 Correct 14 ms 8576 KB Output is correct
15 Correct 10 ms 4864 KB Output is correct
16 Correct 9 ms 4864 KB Output is correct
17 Correct 14 ms 7552 KB Output is correct
18 Correct 10 ms 4452 KB Output is correct
19 Correct 18 ms 9984 KB Output is correct
20 Correct 13 ms 7808 KB Output is correct
21 Correct 18 ms 9976 KB Output is correct