oj.uz

Submission #27841

# Submission time Handle Problem Language Result Execution time Memory
27841 2017-07-14T07:54:08 Z rondojim Match (CEOI16_match) C++14
37 / 100
 1206 ms 2168 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2168 KB Output is correct
2 Correct 0 ms 2168 KB Output is correct
3 Correct 0 ms 2168 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2168 KB Output is correct
2 Correct 0 ms 2168 KB Output is correct
3 Correct 0 ms 2168 KB Output is correct
4 Correct 276 ms 2168 KB Output is correct
5 Correct 493 ms 2168 KB Output is correct
6 Correct 39 ms 2168 KB Output is correct
7 Correct 1206 ms 2168 KB Output is correct

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2168 KB Output is correct
2 Correct 0 ms 2168 KB Output is correct
3 Correct 0 ms 2168 KB Output is correct
4 Correct 276 ms 2168 KB Output is correct
5 Correct 493 ms 2168 KB Output is correct
6 Correct 39 ms 2168 KB Output is correct
7 Correct 1206 ms 2168 KB Output is correct
8 Runtime error 0 ms 2168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -