Submission #260531

#	Time	Username	Problem	Language	Result	Execution time	Memory
260531		kimbj0709	Match (CEOI16_match)	C++14	10 / 100	1 ms	1280 KiB

match

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define maxn 100050
int lastpos[maxn][26];
string input;
vector<int> out(maxn,0);
void recursive(int l,int r){
  if(l>=r){
    return;
  }
  if(input.at(l)==input.at(r)){
    out[r] = 1;
    recursive(l+1,r-1);
    return;
  }
  int pos = lastpos[r][input.at(l)-'a'];
  out[pos] = 1;
  recursive(l+1,pos-1);
  recursive(pos+1,r);
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);cout.tie(0);
  cin >> input;
  stack<int> stack1;
  stack1.push(0);
  for(int i=1;i<input.length();i++){
    if(stack1.size()!=0&&input.at(stack1.top())==input.at(i)){
      stack1.pop();
    }
    else{
      stack1.push(i);
    }
  }
  if(stack1.size()!=0){
    cout << -1;
    return 0;
  }
  for(int i=0;i<26;i++){
    int last = -1;
    for(int j=0;j<input.length();j++){
      if(input.at(j)==('a'+i)){
        last = j;
      }
      lastpos[j][i] = last; 
    }
  }
  recursive(0,input.length()-1);
  for(int i=0;i<input.length();i++){
    if(out[i]==1){
      cout << ')';
    }
    else{
      cout << '(';
    }
  }

}

Compilation message (stderr)

match.cpp: In function 'int32_t main()':
match.cpp:28:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=1;i<input.length();i++){
               ~^~~~~~~~~~~~~~~
match.cpp:42:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0;j<input.length();j++){
                 ~^~~~~~~~~~~~~~~
match.cpp:50:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<input.length();i++){
               ~^~~~~~~~~~~~~~~

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