제출 #260544

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
260544		kimbj0709	괄호 문자열 (CEOI16_match)	C++14	100 / 100	32 ms	23288 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);
int right(int r,char c){
  if(lastpos[r][c-'a']!=-1){
    return lastpos[r][c-'a'];
  }
  int ret = -1;
  if(r-2>=0&&input.at(r)==input.at(r-1)){
    if(input.at(r-2)==c){
      ret = r-2;
    }
    else{
      ret = right(r-2,c);
    }
  }
  else{
    int pos = right(r-1,input.at(r))-1;;
    if(input.at(pos)==c){
      ret = pos;
    }
    else{
      ret = right(pos,c);
    }
  }
  lastpos[r][c-'a'] = ret;
  return ret;
}
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 = right(r,input.at(l));
  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++){
    for(int j=0;j<input.length();j++){
      lastpos[j][i] = -1;
    }
  }
  recursive(0,input.length()-1);
  for(int i=0;i<input.length();i++){
    if(out[i]==1){
      cout << ')';
    }
    else{
      cout << '(';
    }
  }

}

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

match.cpp: In function 'int32_t main()':
match.cpp:53:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=1;i<input.length();i++){
               ~^~~~~~~~~~~~~~~
match.cpp:66:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0;j<input.length();j++){
                 ~^~~~~~~~~~~~~~~
match.cpp:71: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: 27 / 27
• Subtask 3: 63 / 63