Submission #726538

#	Time	Username	Problem	Language	Result	Execution time	Memory
726538		viwlesxq	Homework (CEOI22_homework)	C++17	100 / 100	85 ms	37712 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef int64_t ll;
typedef string str;

int n, commas_gone;
str s;
vector <int> comma;

pair <int, int> get_range(int i) {
  if (s[i] == '?') {
    return {1, n};
  } else if (s[i + 2] == 'x') {
    pair <int, int> range_left = get_range(i + 4), range;
    pair <int, int> range_right = get_range(comma[commas_gone++] + 1);
    range.second = max(range_left.second, range_right.second);
    range.first = range_left.first + range_right.first;
    return range;
  } else {
    pair <int, int> range_left = get_range(i + 4), range;
    pair <int, int> range_right = get_range(comma[commas_gone++] + 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;
  for (int i = 0; i < (int)s.size(); ++i) {
    if (s[i] == ',') {
      comma.push_back(i);
    }
  }
  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: 13 / 13
• Subtask 4: 30 / 30
• Subtask 5: 34 / 34