제출 #110861

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
110861		mosesmayer	괄호 문자열 (CEOI16_match)	C++17	100 / 100	19 ms	11776 KiB

match

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int mxsz = 1e5 + 5;

int n;
char S[mxsz], ans[mxsz];
int lft[mxsz][26];

void prec(){
	for (int i = 1, p; i <= n; i++){
		p = S[i] - 'a';
		lft[i][p] = i;
		if (i - 1)
			for (int j = 0, x = lft[i-1][p]; j < 26; j++)
				if (x && (j^p))
					lft[i][j] = lft[x-1][j]; // link to before prev to be able to match prev with i
	}
	//for (int i = 1; i <= n; i++) for (int j = 0; j < 26; j++) cout << lft[i][j] << " \n"[j==25];
}
stack<int> st;
inline bool CHECK(){
	for (int i = 1, p; i <= n; i++){
		p = S[i] - 'a';
		if (st.empty() || st.top() != p) st.push(p);
		else st.pop();
	}
	return st.empty();
}
void rec(int l, int r){
	//cout << l << ' ' << r << '\n';
	if (l > r) return;
	int pos = lft[r][S[l] - 'a'];
	ans[l] = '('; ans[pos] = ')';
	rec(l+1, pos - 1); rec(pos+1, r);
}
int main(){
	scanf("%s", S+1);
	n = strlen(S+1);
	ans[n+1] = '\0';
	if (!CHECK()) return 0 * printf("-1");
	prec();
	rec(1,n);
	puts(ans+1);
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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