oj.uz

Submission #609770

# Submission time Handle Problem Language Result Execution time Memory
609770 2022-07-27T21:39:09 Z DanerZein Match (CEOI16_match) C++14
37 / 100
 2000 ms 12768 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 0 ms 328 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Correct 5 ms 11956 KB Output is correct
5 Correct 5 ms 11988 KB Output is correct
6 Correct 5 ms 11984 KB Output is correct
7 Correct 6 ms 12068 KB Output is correct

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Correct 5 ms 11956 KB Output is correct
5 Correct 5 ms 11988 KB Output is correct
6 Correct 5 ms 11984 KB Output is correct
7 Correct 6 ms 12068 KB Output is correct
8 Correct 6 ms 11988 KB Output is correct
9 Correct 17 ms 11988 KB Output is correct
10 Correct 11 ms 12096 KB Output is correct
11 Correct 8 ms 11976 KB Output is correct
12 Correct 175 ms 12300 KB Output is correct
13 Correct 83 ms 12316 KB Output is correct
14 Correct 952 ms 12580 KB Output is correct
15 Correct 8 ms 12368 KB Output is correct
16 Correct 9 ms 12376 KB Output is correct
17 Correct 103 ms 12472 KB Output is correct
18 Correct 17 ms 12372 KB Output is correct
19 Correct 1464 ms 12768 KB Output is correct
20 Correct 672 ms 12448 KB Output is correct
21 Execution timed out 2093 ms 12556 KB Time limit exceeded
22 Halted 0 ms 0 KB -