Submission #27841

#	Time	Username	Problem	Language	Result	Execution time	Memory
27841		rondojim	Match (CEOI16_match)	C++14	37 / 100	1206 ms	2168 KiB

match

#include <stdio.h>
#include <vector>
#include <stack>
#include <string.h>

using namespace std;

const int MAXN = 2e3 + 5, MAXA = 30;

int N, p[MAXA][MAXN];
char s[MAXN], res[MAXN];

bool valid(int i, int j){
  stack<char> st;
  for(int k=i; k<=j; ++k){
    if(st.empty()) st.push(s[k]);
    else if(st.top() == s[k]) st.pop();
    else st.push(s[k]);
  }
  return st.empty();
}

int n(char c){ return c - 'a'; }

void solve(){
  for(int i=N-1; i>=0; --i){
    p[n(s[i])][i] = i;
    for(int j=i-1; j>=0; --j)
      if(p[n(s[j])][i] == -1  && valid(j + 1, i)) p[n(s[j])][i] = j;
  }
}

void Fill(int i, int j){
  if(i > j) return;
  int k = p[n(s[i])][j];
  res[i] = '(', res[k] = ')';
  Fill(i + 1, k - 1); Fill(k + 1, j);
}

int main(){
  scanf("%s", s);
  N = strlen(s);
  if(!valid(0, N - 1)){ puts("-1"); return 0; }
  memset(p, -1, sizeof(p));
  solve();
  Fill(0, N - 1);
  puts(res);
  return 0;
}

Compilation message (stderr)

match.cpp: In function 'int main()':
match.cpp:41:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", s);
                 ^

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