Submission #1127491

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127491		pemguimn	Homework (CEOI22_homework)	C++17	10 / 100	450 ms	486216 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>

using namespace std;

const int N = 6e6 + 5;

string s; int cntq;
int id = 0, t[N], mp[N]; vector<int> adj[N];

bool c1(){
    return cntq <= 9;
}

namespace sub1{
    vector<int> leaf;
    int w[N], cnt[N];
    int dfs(int i){
        if(!adj[i].empty()){
            int a = dfs(adj[i][0]), b = dfs(adj[i][1]);
            if(t[i] == 1) return max(a, b);
            return min(a, b);
        } else{
            return w[i];
        }
    }
    void solve(){
        for(int i = 1; i <= id; i++){
            if(adj[i].empty()) leaf.push_back(i);
        }
        vector<int> p(cntq); iota(p.begin(), p.end(), 1);
        assert(leaf.size() == p.size());
        do{
            for(int i = 0; i <= id; i++) w[i] = 0;
            for(int i = 0; i < cntq; i++) w[leaf[i]] = p[i];
            cnt[dfs(1)]++;
        } while(next_permutation(p.begin(), p.end()));
        int dist = 0;
        for(int i = 1; i <= cntq; i++) dist += (cnt[i] > 0);
        cout << dist << '\n';
    }

}

bool c2(){
    return cntq <= 16;
}

//namespace sub2{
//    const int MASK = 1 << 16;
//    set<int> a[N][MASK];
//    int w[N], cnt[N];
//    int dfs(int i){
//        if(!adj[i].empty()){
//            int a = dfs(adj[i][0]), b = dfs(adj[i][1]);
//            if(t[i] == 1) return max(a, b);
//            return min(a, b);
//        } else{
//            return w[i];
//        }
//    }
//    void solve(){
//        dfs(1);
//        cout << s[1].size() << '\n';
//    }
//
//}

int cntmn = 0, cntmx = 0, cntleaf = 0;
int dnc(int l, int r){
    ++id; int cur = id;
    if(r - l == 0) t[id] = 0, cntleaf++;
    else{
        if(s[l + 1] == 'i') t[cur] = -1, cntmn++;
        else t[cur] = 1, cntmx++;
        adj[cur].push_back(dnc(l + 4, (s[l + 4] == '?' ? l + 4 : mp[l + 7])));
        adj[cur].push_back(dnc((s[r - 1] == '?' ? mp[r - 1] : mp[r - 1] - 3), r - 1));
    }
    return cur;
}

namespace heur{
    void solve(){
        if(cntmn == 0 || cntmx == 0) cout << 1 << '\n';
        else cout << cntleaf - 1 << '\n';
    }
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    #define task "MINMAX"
    if(fopen(task ".inp", "r")){
        freopen(task ".inp", "r", stdin);
        freopen(task ".out", "w", stdout);
    }

    // Input Output

    cin >> s;
    for(char c : s) cntq += (c =='?');

    stack<int> st;
    for(int i = 0; i < s.size(); i++) mp[i] = i;
    for(int i = 0; i < s.size(); i++){
        if(s[i] == '(') st.push(i);
        else if(s[i] == ')') mp[st.top()] = i, mp[i] = st.top(), st.pop();
    }
    dnc(0, s.size() - 1);
    // Subtask

    {
        if(c1()) return sub1::solve(), 0;
        heur::solve();
    }
    return 0;
}

/*
min(min(?,?),min(?,?))

max(?,max(?,min(?,?)))

min(max(?,?),min(?,max(?,?)))
*/

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:95:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |         freopen(task ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:96:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |         freopen(task ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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