Submission #677149

#	Time	Username	Problem	Language	Result	Execution time	Memory
677149		stanislavpolyn	Homework (CEOI22_homework)	C++17	23 / 100	1093 ms	396968 KiB

Main

#include <bits/stdc++.h>

#define fr(i, a, b) for (int i = (a); i <= (b); ++i)
#define rf(i, a, b) for (int i = (a); i >= (b); --i)
#define fe(x, y) for (auto& x : y)

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mt make_tuple

#define all(x) (x).begin(), (x).end()
#define pw(x) (1LL << (x))
#define sz(x) (int)(x).size()

using namespace std;

mt19937_64 rng(228);

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define fbo find_by_order
#define ook order_of_key

template <typename T>
bool umn(T& a, T b) {
    return a > b ? (a = b, 1) : 0;
}
template <typename T>
bool umx(T& a, T b) {
    return a < b ? (a = b, 1) : 0;
}

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename T>
using ve = vector<T>;

#ifndef LOCAL
const int N = 5e6 + 5;
#else
const int N = 1005;
#endif

string s;
int last[N];
int p[N];
int root;
ve<int> g[N];
int n;
ve<int> pos;
int val[N];
ve<int> ver;
ve<int> order;

void dfs(int v) {
    fe (to, g[v]) {
        dfs(to);
    }
    order.pb(v);
}

int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
    ios::sync_with_stdio(0);
    cin.tie(0);
#endif

    cin >> s;

    last[0] = -1;
    int bal = 0;
    fr (i, 0, sz(s) - 1) {
        if (s[i] == '(' || s[i] == ')') {
            if (s[i] == '(') {
                bal++;
            } else {
                bal--;
            }
            if (s[i] == '(') {
                p[i] = last[bal - 1];
                last[bal] = i;
            }
        }
        if (s[i] == '?') {
            pos.pb(i);
            p[i] = last[bal];
            n++;
        }
    }

    fr (i, 0, sz(s) - 1) {
        if (s[i] == '(' || s[i] == '?') {
            if (p[i] == -1) {
                root = i;
            } else {
                g[p[i]].pb(i);
            }
            ver.pb(i);
//            cout << i << " " << p[i] << "\n";
        }
    }

    dfs(root);

    ve<bool> possib(n + 1);

    fr (mask, 0, pw(n - 1) - 1) {
        fr (me, 0, sz(pos) - 1) {
            fe (x, ver) val[x] = -1;

            int x = 1;
            int ptr = 0;
            fr (i, 0, n - 2) {
                if (ptr == me) ptr++;

                if (mask & pw(i)) {
                    val[pos[ptr++]] = 1;
                } else {
                    val[pos[ptr++]] = 0;
                    x++;
                }
            }

            val[pos[me]] = 2;

            bool bad = 0;
            fe (v, order) {
                if (s[v] == '?') continue;

                assert(val[v] == -1);

                if (val[g[v][1]] == 2) swap(g[v][0], g[v][1]);

                if (val[g[v][0]] == 2) {
                    if (s[v - 1] == 'x' && val[g[v][1]] == 1) {
                        bad = 1;
                        break;
                    }
                    if (s[v - 1] == 'n' && val[g[v][1]] == 0) {
                        bad = 1;
                        break;
                    }
                    val[v] = 2;
                } else {
                    if (s[v - 1] == 'x') {
                        val[v] = max(val[g[v][0]], val[g[v][1]]);
                    } else {
                        val[v] = min(val[g[v][0]], val[g[v][1]]);
                    }
                }
            }

            if (!bad) {
                possib[x] = 1;
            }
        }
    }

    int ans = 0;
    fr (i, 1, n) {
        if (possib[i]) {
            ans++;
        }
    }
    cout << ans << "\n";

    return 0;
}

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