제출 #1327784

#제출 시각아이디문제언어결과실행 시간메모리
1327784shirokuma5Homework (CEOI22_homework)C++20
10 / 100
1100 ms116824 KiB
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
using namespace std;

string s;
vector<int> idx, quest, kakko;

void print(const vector<int> &a) {
    for (int x : a) cerr << " " << x;
    cerr << endl;
}

// [l, r) を計算
int calc(int l = 0, int r = s.size()) {
    if (r == l + 1) return idx[quest[l]];
    int left = 0, right = 0;
    if (s[l+4] == '?') left = idx[quest[l+4]];
    else left = calc(l+4,kakko[l+7]+1);
    if (s[r-2] == '?') right = idx[quest[r-2]];
    else right = calc(kakko[r-2]-3, r-1);
    int ret = 0;
    if (s[l+1] == 'i') ret = min(left, right);
    else ret = max(left, right);
    //cerr << "calc " << l << " " << r << " " << ret << endl;
    //if (l == 0 && r == s.size()) print(idx);
    return ret;
}

int main() {
    cin >> s;
    int n = 0; quest.assign(s.size(), -1); kakko.assign(s.size(), -1);
    stack<int> st;
    rep(i, s.size()) {
        if (s[i] == '?') {
            quest[i] = n; n++;
        }
        else if (s[i] == '(') st.push(i);
        else if (s[i] == ')') {
            kakko[i] = st.top(); kakko[st.top()] = i; st.pop();
        }
    }

    idx.resize(n);
    rep(i, n) idx[i] = i + 1;

    set<int> se;
    do {
        se.insert(calc());
    } while (next_permutation(idx.begin(), idx.end()));
    cout << se.size() << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...