Submission #1124191

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124191		dynam1c	Homework (CEOI22_homework)	C++20	23 / 100	1101 ms	120696 KiB

Main

#include <bits/stdc++.h>
using namespace std;
int popcount(int x) { return __builtin_popcount(x); }
enum Type { Num, Min, Max };
struct Node {
  Type type;
  Node* left = nullptr;
  Node* right = nullptr;

  int eval(vector<int>::iterator& it) {
    if (type == Num)
      return *it++;
    int l = left->eval(it);
    int r = right->eval(it);
    if (type == Min)
      return min(l, r);
    return max(l, r);
  }
};
int main() {
  string s;
  cin >> s;
  int cur = 0;
  
  int n = 0;
  function<Node*()> parse = [&]() {
    if (s[cur] == '?') {
      n++;
      cur++;
      return new Node{Num};
    }
    Type type = s[cur+1] == 'i' ? Min : Max;
    cur += 4;
    Node* left = parse();
    cur += 1;
    Node* right = parse();
    cur += 1;
    return new Node{type, left, right};
  };

  Node* root = parse();
  vector<int> val(n);
  vector<bool> res(n);
  for (int i = 0; i < n; i++)
    for (int b = 0; b < (1<<n); b++) {
      for (int j = 0; j < n; j++)
        val[j] = b>>j&1 ? 2 : 0;
      val[i] = 1;
      auto it = val.begin();
      if (root->eval(it) == 1)
        res[popcount(b) - (b>>i&1)] = true;
    }
  cout << accumulate(res.begin(), res.end(), 0) << endl;
}

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