Submission #63161

#	Time	Username	Problem	Language	Result	Execution time	Memory
63161		khsoo01	Match (CEOI16_match)	C++11	100 / 100	22 ms	12652 KiB

match

#include<bits/stdc++.h>
using namespace std;
const int N = 100005;
 
int n, dt[N][26];
char a[N], b[N];
 
void solve (int S, int E) {
	if(S>E) return;
	int T = dt[E][a[S]];
	if(T <= S) {
		puts("-1");
		exit(0);
	}
	b[S] = '(';
	b[T] = ')';
	solve(S+1, T-1);
	solve(T+1, E);
}
 
int main()
{
	scanf("%s",a+1);
	n = strlen(a+1);
	for(int i=1;i<=n;i++) {
		a[i] -= 'a';
		if(i == 1 || dt[i-1][a[i]] < 2) {
			for(int j=0;j<26;j++) {
				dt[i][j] = -1;
			}
		}
		else {
			int T = dt[i-1][a[i]] - 1;
			for(int j=0;j<26;j++) {
				dt[i][j] = dt[T][j];
			}
		}
		dt[i][a[i]] = i;
	}
	solve(1, n);
	printf("%s",b+1);
}

Compilation message (stderr)

match.cpp: In function 'void solve(int, int)':
match.cpp:10:20: warning: array subscript has type 'char' [-Wchar-subscripts]
  int T = dt[E][a[S]];
                    ^
match.cpp: In function 'int main()':
match.cpp:27:28: warning: array subscript has type 'char' [-Wchar-subscripts]
   if(i == 1 || dt[i-1][a[i]] < 2) {
                            ^
match.cpp:33:24: warning: array subscript has type 'char' [-Wchar-subscripts]
    int T = dt[i-1][a[i]] - 1;
                        ^
match.cpp:38:13: warning: array subscript has type 'char' [-Wchar-subscripts]
   dt[i][a[i]] = i;
             ^
match.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",a+1);
  ~~~~~^~~~~~~~~~

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