oj.uz

답안 #1117840

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1117840 2024-11-24T08:49:40 Z vjudge1 괄호 문자열 (CEOI16_match) C++17
10 / 100
 487 ms 428 KB 
#include <bits/stdc++.h>
using namespace std;

bool isValid(const string &str) {
  int n = 0;
  for (const char &c : str) {
    if (c == '(') {
      n++;
    } else if (n == 0) {
      return false;
    } else {
      n--;
    }
  }

  return n == 0;
}

int main() {
  string s;
  cin >> s;
  uint32_t limit = (1 << s.size());
  // cout << "LIMIT: " << limit << '\n';
  bool found = false;
  string ans;
  ans.resize(s.size());

  for (uint32_t bitmask = 0; bitmask < limit; bitmask += 1) {
    string b;
    b.assign(s.size(), 'x');
    for (uint32_t i = 0; i < s.size(); i++) {
      if (bitmask & (1 << i)) {
        b[i] = '(';
      } else {
        b[i] = ')';
      }

      for (uint32_t j = 0; j < i; j++) {
        if (b[j] == '(' and b[i] == ')' and
            isValid(b.substr(j + 1, i - j - 1)) and s[i] != s[j]) {
          // cout << b << " is wrong for: " << b.substr(j + 1, i - j - 1)
          //      << " and " << i << ", " << j << '\n';
          goto next_permutation;
        }
      }
    }

    if (!isValid(b)) {
      // cout << b << " is invalid" << '\n';
      goto next_permutation;
    }

    if (!found) {
      ans = b;
      // cout << "new answer: " << b << '\n';
      found = true;
    } else if (ans > b) {
      ans = b;
      // cout << "new answer: " << b << '\n';
    }

  next_permutation:
    continue;
  }

  if (!found) {
    cout << -1 << '\n';
  } else {
    cout << ans << '\n';
  }
  return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 63 ms 428 KB Output is correct
3 Correct 5 ms 336 KB Output is correct

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 63 ms 428 KB Output is correct
3 Correct 5 ms 336 KB Output is correct
4 Incorrect 487 ms 336 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 63 ms 428 KB Output is correct
3 Correct 5 ms 336 KB Output is correct
4 Incorrect 487 ms 336 KB Output isn't correct
5 Halted 0 ms 0 KB -