Submission #609770

#	Time	Username	Problem	Language	Result	Execution time	Memory
609770		DanerZein	Match (CEOI16_match)	C++14	37 / 100	2093 ms	12768 KiB

match

#include <bits/stdc++.h>
using namespace std;
const int MAX_N=1e5+10;
int n;
string x;
string ans;
int rabc[MAX_N][30];
int maxr(int l,int r){
  rabc[r][x[r]-'a']=r;
  if(rabc[r][x[l]-'a']!=-1) return rabc[r][x[l]-'a'];
  stack<int> st;
  st.push(r);
  for(int j=r-1;j>=l;j--){
    if(st.empty() || x[st.top()]!=x[j]){
      st.push(j);
    }
    else{
      int i=st.top();
      st.pop();
      if(st.empty()){
	if(rabc[r][x[j]-'a']==-1) rabc[r][x[j]-'a']=i;
	if(rabc[r][x[l]-'a']!=-1)
	  break;
      }
    }
  }
  return rabc[r][x[l]-'a'];
}
void match(int l,int r){
  if(l>=r){
    return;
  }
  int id=maxr(l,r);
  ans[l]='('; ans[id]=')';
  match(id+1,r);
  match(l+1,id-1);
}
int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  cin>>x;
  n=x.size();
  stack<char> st;
  for(int j=0;j<n;j++){
    if(st.empty() || st.top()!=x[j]){
      st.push(x[j]);
    }
    else{
      st.pop();
    }
  }
  if(st.empty()){
    memset(rabc,-1,sizeof rabc);
    ans.resize(n);
    match(0,n-1);
    cout<<ans<<endl;
  }
  else cout<<"-1\n";
  
}

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