oj.uz

답안 #48085

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
48085 2018-05-10T04:19:19 Z Extazy 괄호 문자열 (CEOI16_match) C++17
37 / 100
 2000 ms 1020 KB 
#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

const int N = 100007;

int n;
char a[N],ans[N];

bool can(int l, int r) {
  stack < char > s;
  int i;

  for(i=l;i<=r;i++) {
    if(!s.empty() && s.top()==a[i]) s.pop();
    else s.push(a[i]);
  }

  return s.empty();
}

void solve(int l, int r) {
  if(l>r) return;

  for(int i=r;i>=l;i--) {
    if(a[i]==a[l]) if(can(l+1,i-1)) {
      solve(l+1,i-1);
      solve(i+1,r);
      ans[l]='(';
      ans[i]=')';
      return;
    }
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int i;

  scanf("%s", a+1);
  n=strlen(a+1);

  if(!can(1,n)) {
    printf("-1\n");
    return 0;
  }
    
  solve(1,n);
  for(i=1;i<=n;i++) {
    printf("%c", ans[i]);
  }
  printf("\n");

  return 0;
}

Compilation message

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

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 412 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 412 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 4 ms 544 KB Output is correct
7 Correct 21 ms 544 KB Output is correct

Subtask #3
0 / 63.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 412 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 4 ms 544 KB Output is correct
7 Correct 21 ms 544 KB Output is correct
8 Correct 207 ms 620 KB Output is correct
9 Execution timed out 2059 ms 1020 KB Time limit exceeded
10 Halted 0 ms 0 KB -