oj.uz

Submission #52936

# Submission time Handle Problem Language Result Execution time Memory
52936 2018-06-27T08:13:45 Z 김세빈(#1383) Match (CEOI16_match) C++11
0 / 100
 2 ms 616 KB 
#include <bits/stdc++.h>

using namespace std;

char str[101010], ans[101010];
int F[101010], K[33][101010];
int C[101010], T[33];
vector <char> V;
int n;

int find_next(int p)
{
	if(F[p]) return F[p];
	
	int ret = p+1;
	
	for(;ret < n && str[p] != str[ret];) ret = find_next(ret) + 1;
	
	return F[p] = ret;
}

int main()
{
	int i,j;
	
	scanf("%s",str);
	
	for(n=0;str[n];n++);
	
	for(i=0;i<n;i++) find_next(i);
	
	for(i=0;i<26;i++){
		for(j=n-1;j>=0;j--){
			if(str[j]-'a' == i) K[i][j] = j;
			else if(F[j]+1 >= n) K[i][j] = n;
			else{
				K[i][j] = K[i][F[j]+1];
			}
		}
	}
	
	for(i=n-1;i>=0;i--){
		C[i] = ++ T[str[i]-'a'];
	}
	
	for(i=0;i<26;i++) T[i] = 0;
	
	for(i=0;i<n;i++){
		if(V.empty() || V.back() != str[i]){
			V.push_back(str[i]);
			ans[i] = '(';
			T[str[i]-'a'] ++;
		}
		else{
			if(F[i] < n-1 && K[str[i]-'a'][F[i]+1] < n && C[K[str[i]-'a'][F[i]+1]] >= T[str[i]-'a']){
				V.push_back(str[i]);
				ans[i] = '(';
				T[str[i]-'a'] ++;
			}
			else{
				V.pop_back();
				ans[i] = ')';
				T[str[i]-'a'] --;
			}
		}
//		ans[i+1] = '\0';
//		printf("%s\n",ans);
	}
	
	ans[n] = '\0';
	
	if(V.empty()) printf("%s\n",ans);
	else printf("-1\n");
	
	return 0;
}

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Incorrect 2 ms 616 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Incorrect 2 ms 616 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Incorrect 2 ms 616 KB Output isn't correct
3 Halted 0 ms 0 KB -