Submission #127756

#	Time	Username	Problem	Language	Result	Execution time	Memory
127756		sealnot123	Match (CEOI16_match)	C++14	100 / 100	19 ms	11724 KiB

match

#include<bits/stdc++.h>
#define x first
#define y second
#define all(x) (x).begin(),(x).end()
#define SZ(x) (int)(x).size()
#define push_back pb
#define emplace_back eb
using namespace std;
typedef long long LL;
typedef double DD;
typedef long double LD;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
const int N = 100007;
int dp[N][26];
char str[N], ans[N];
stack<char> sta;
int n;
void play(int l, int r){
	if(l>r) return ;
	ans[l] = '(';
	int a = dp[r][str[l]-'a'];
	ans[a] = ')';
	play(l+1, a-1); play(a+1, r);
}
int main(){
	int a,b,c,d,i,j,k,l;
	scanf("%s",str+1);
	n = strlen(str+1);
	for(i=1;i<=n;i++){
		dp[i][str[i]-'a'] = i;
		a = dp[i-1][str[i]-'a'];
		if(!a) continue;
		for(j=0;j<26;j++) dp[i][j] = max(dp[i][j], dp[a-1][j]);
	}
	// check
	for(i=1;i<=n;i++){
		if(!sta.empty() && sta.top() == str[i]) sta.pop();
		else sta.push(str[i]);
	}
	if(!sta.empty()){
		printf("-1");
		return 0;
	}
	// do ans
	play(1, n);
	printf("%s",ans+1);
	return 0;
}
/*
abbccddabbccdd
abbacabbac
accaccacca
aaaabbbb
aaabcaacba (()((())))
*/

Compilation message (stderr)

match.cpp: In function 'int main()':
match.cpp:27:8: warning: unused variable 'b' [-Wunused-variable]
  int a,b,c,d,i,j,k,l;
        ^
match.cpp:27:10: warning: unused variable 'c' [-Wunused-variable]
  int a,b,c,d,i,j,k,l;
          ^
match.cpp:27:12: warning: unused variable 'd' [-Wunused-variable]
  int a,b,c,d,i,j,k,l;
            ^
match.cpp:27:18: warning: unused variable 'k' [-Wunused-variable]
  int a,b,c,d,i,j,k,l;
                  ^
match.cpp:27:20: warning: unused variable 'l' [-Wunused-variable]
  int a,b,c,d,i,j,k,l;
                    ^
match.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",str+1);
  ~~~~~^~~~~~~~~~~~

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