Submission #1014726

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014726		atom	Homework (CEOI22_homework)	C++17	10 / 100	1073 ms	131740 KiB

Main

#include "bits/stdc++.h"
// @JASPER'S BOILERPLATE
using namespace std;
using ll = long long;

#ifdef JASPER
#include "debug.h"
#else
#define debug(...) 166
#endif

const int N = 1e6 + 5;

int n, sz;
string s; 
vector <int> c;

struct Node {
    int t;
    Node *l, *r;
    Node() {
        t = -1;
        l = r = nullptr;
    }
};

Node* make(int& i) {
    Node* cur = new Node();
    if (s[i] == '?') {
        ++i;
        cur->t = n++;
        return cur;
    }    

    if (s[i + 1] == 'i') {
        cur->t = -1;
    }
    else {
        cur->t = -2;
    }
    i += 4;
    cur->l = make(i);
    ++i;
    cur->r = make(i);
    ++i;

    return cur;
}

int dfs(Node* tr) {
    if (tr->t >= 0) 
        return c[tr->t];
    int x = 0, y = 0;
    if (tr->l != nullptr) 
        x = dfs(tr->l);
    if (tr->r != nullptr)
        y = dfs(tr->r);
    if (tr->t == -1) return min(x, y);
    else return max(x, y);
}


signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    
    #ifdef JASPER
        freopen("in1", "r", stdin);
    #endif

    cin >> s;
    sz = s.size();
    
    int p = 0;
    Node* tr = make(p);

    c.resize(n);
    iota(c.begin(), c.end(), 1);

    vector <int> vals;
    do {
        vals.push_back(dfs(tr));
    } while (next_permutation(c.begin(), c.end()));

    sort(vals.begin(), vals.end());
    vals.resize(unique(vals.begin(), vals.end()) - vals.begin());

    cout << (int) vals.size() << "\n";
    // cout << dfs(tr) << "\n";

    return 0;
}

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