Submission #726537

#	Time	Username	Problem	Language	Result	Execution time	Memory
726537		viwlesxq	Homework (CEOI22_homework)	C++17	53 / 100	1036 ms	14112 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef int64_t ll;
typedef string str;

int n;
str s;

pair <int, int> get_range(int i) {
  if (s[i] == '?') {
    return {1, n};
  } else if (s[i + 2] == 'x') {
    int comma, cnt = 0;
    for (int j = i + 4; ; ++j) {
      if (s[j] == ',' && !cnt) {
        comma = j;
        break;
      }
      if (s[j] == '(') {
        ++cnt;
      } 
      if (s[j] == ')') {
        --cnt;
      }
    }
    pair <int, int> range_left = get_range(i + 4), range;
    pair <int, int> range_right = get_range(comma + 1);
    range.second = max(range_left.second, range_right.second);
    range.first = range_left.first + range_right.first;
    return range;
  } else {
    int comma, cnt = 0;
    for (int j = i + 4; ; ++j) {
      if (s[j] == ',' && !cnt) {
        comma = j;
        break;
      }
      if (s[j] == '(') {
        ++cnt;
      } 
      if (s[j] == ')') {
        --cnt;
      }
    }
    pair <int, int> range_left = get_range(i + 4), range;
    pair <int, int> range_right = get_range(comma + 1);
    range.second = range_left.second + range_right.second - n - 1;
    range.first = min(range_left.first, range_right.first);
    return range;
  }
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> s;
  n = count(s.begin(), s.end(), '?');
  pair <int, int> range = get_range(0);
  cout << range.second - range.first + 1;
}

• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 0 / 13
• Subtask 4: 30 / 30
• Subtask 5: 0 / 34