제출 #90643

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
90643		jangwonyoung	괄호 문자열 (CEOI16_match)	C++14	100 / 100	37 ms	7412 KiB

match

#include<iostream>
#include<stack>
#include<set>
using namespace std;
string s,b;
int n;
int f[100001];
stack<char>st;
stack<int>cut;
set<pair<int,int> >g[226];
int par[100001];
int find(int x){
	if(par[x]!=x) par[x]=find(par[x]);
	return par[x];
}
void join(int u,int v){
	u=find(u);v=find(v);
	par[u]=v;
}
int main(){
	ios::sync_with_stdio(false);
	cin >> s;
	b=s;
	n=s.size();
	par[n]=n;
	for(int i=0; i<n ;i++){
		par[i]=i;
		if(st.empty() || st.top()!=s[i]) st.push(s[i]);
		else st.pop();
	}
	if(!st.empty()){
		cout << "-1\n";
		return 0;
	}
	for(int i=n-1; i>=0 ;i--){
		f[i]=-1;
		int en=i+1;
		while(en<n && en>=0){
			if(s[i]==s[en]){
				f[i]=en+1;
				break;
			}
			en=f[en];
		}
	}
	for(int i=0; i<n ;i++){
		if(f[i]!=-1) join(i,f[i]);
	}
	for(int i=0; i<n ;i++){
		g[s[i]].insert({find(i+1),i});
	}
	cut.push(n);
	for(int i=0; i<n ;i++){
		if(i==cut.top()){
			cut.pop();
			continue;
		}
		pair<int,int>tmp={find(i),cut.top()};
		auto it=g[s[i]].lower_bound(tmp);
		--it;
		b[i]='(';
		b[it->second]=')';
		cut.push(it->second);
		g[s[i]].erase(it);
	}
	cout << b << endl;
}

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

match.cpp: In function 'int main()':
match.cpp:50:9: warning: array subscript has type 'char' [-Wchar-subscripts]
   g[s[i]].insert({find(i+1),i});
         ^
match.cpp:59:17: warning: array subscript has type 'char' [-Wchar-subscripts]
   auto it=g[s[i]].lower_bound(tmp);
                 ^
match.cpp:64:9: warning: array subscript has type 'char' [-Wchar-subscripts]
   g[s[i]].erase(it);
         ^

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