Submission #1117840

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117840		vjudge1	Match (CEOI16_match)	C++17	10 / 100	487 ms	428 KiB

match

#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 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 63