Submission #115244

#	Time	Username	Problem	Language	Result	Execution time	Memory
115244		sebinkim	Match (CEOI16_match)	C++14	100 / 100	32 ms	1400 KiB

match

#include <bits/stdc++.h>

using namespace std;

char s[101010];
int dp[101010];
int n;

void die()
{
	printf("-1\n");
	exit(0);
}

int make(int p, int r)
{
	int i, ret;
	
	ret = -1;
	for(i=p+1; i<r; i=dp[i]+1){
		if(s[i] == s[p]) ret = i;
	}
	
	if(ret == -1) die();
	
	s[p] = '('; s[ret] = ')';
	
	for(i=p+1; i<ret; ){
		if(dp[i] == n) die();
		i = make(i, ret) + 1;
		if(i > ret) die();
	}
	
	return ret;
}

int main()
{
	int i, j;
	
	scanf("%s", s);
	
	n = strlen(s);
	
	for(i=n-1; i>=0; i--){
		for(j=i+1; s[i] != s[j] && j<n; j=dp[j]+1);
		dp[i] = j;
	}
	
	for(i=0; i<n; ){
		if(dp[i] == n) die();
		i = make(i, n) + 1;
		if(i > n) die();
	}
	
	printf("%s\n", s);
	
	return 0;
}

Compilation message (stderr)

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

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