oj.uz

Submission #115244

# Submission time Handle Problem Language Result Execution time Memory
115244 2019-06-06T08:56:21 Z sebinkim Match (CEOI16_match) C++14
100 / 100
 32 ms 1400 KB 
#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

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

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

Subtask #2
27.0 / 27.0

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

Subtask #3
63.0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 3 ms 896 KB Output is correct
13 Correct 3 ms 1024 KB Output is correct
14 Correct 4 ms 1152 KB Output is correct
15 Correct 32 ms 1400 KB Output is correct
16 Correct 32 ms 1276 KB Output is correct
17 Correct 5 ms 1252 KB Output is correct
18 Correct 9 ms 1024 KB Output is correct
19 Correct 4 ms 1152 KB Output is correct
20 Correct 2 ms 1024 KB Output is correct
21 Correct 5 ms 1280 KB Output is correct