QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#429604#8770. ComparatorrniyaAC ✓250ms82372kbC++236.9kb2024-06-02 17:57:442024-06-02 17:57:46

Judging History

你现在查看的是最新测评结果

  • [2024-06-02 17:57:46]
  • 评测
  • 测评结果:AC
  • 用时:250ms
  • 内存:82372kb
  • [2024-06-02 17:57:44]
  • 提交

answer

#include <bits/stdc++.h>
#ifdef LOCAL
#include <debug.hpp>
#else
#define debug(...) void(0)
#endif

template <class T> std::istream& operator>>(std::istream& is, std::vector<T>& v) {
    for (auto& e : v) {
        is >> e;
    }
    return is;
}

template <class T> std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
    for (std::string_view sep = ""; const auto& e : v) {
        os << std::exchange(sep, " ") << e;
    }
    return os;
}

template <class T, class U = T> bool chmin(T& x, U&& y) {
    return y < x and (x = std::forward<U>(y), true);
}

template <class T, class U = T> bool chmax(T& x, U&& y) {
    return x < y and (x = std::forward<U>(y), true);
}

template <class T> void mkuni(std::vector<T>& v) {
    std::ranges::sort(v);
    auto result = std::ranges::unique(v);
    v.erase(result.begin(), result.end());
}

template <class T> int lwb(const std::vector<T>& v, const T& x) {
    return std::distance(v.begin(), std::ranges::lower_bound(v, x));
}

using ll = long long;

using namespace std;

vector<vector<int>> value(const string&, int&);
vector<vector<int>> term(const string&, int&);
vector<vector<int>> expression(const string&, int&);

vector<vector<int>> value(const string& s, int& cur) {
    vector res(2, vector<int>(2));
    char c = s[cur++];
    if (islower(c)) {
        assert(c == 'x' or c == 'y');
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                res[i][j] = (c == 'x' ? i : j);
            }
        }
    } else if (isdigit(c)) {
        assert(c == '0' or c == '1');
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                res[i][j] = c - '0';
            }
        }
    } else {
        assert(false);
    }
    return res;
}

vector<vector<int>> term(const string& s, int& cur) {
    if (s[cur] == '(') {
        auto res = expression(s, ++cur);
        assert(s[cur++] == ')');
        return res;
    } else if (s[cur] == '!') {
        auto res = term(s, ++cur);
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                res[i][j] ^= 1;
            }
        }
        return res;
    } else {
        return value(s, cur);
    }
}

// vector<vector<int>> expression(const string& s, int& cur) {
//     auto res = term(s, cur);
//     while (cur < int(s.size())) {
//         char op = s[cur];
//         if (not(op == '=' or op == '&' or op == '|' or op == '^')) {
//             assert(op == ')');
//             break;
//         }
//         cur++;
//         auto R = term(s, cur);
//         for (int i = 0; i < 2; i++) {
//             for (int j = 0; j < 2; j++) {
//                 auto& x = res[i][j];
//                 auto y = R[i][j];
//                 if (op == '=') {
//                     x = x == y;
//                 } else if (op == '&') {
//                     x = x & y;
//                 } else if (op == '|') {
//                     x = x | y;
//                 } else {
//                     assert(op == '^');
//                     x = x ^ y;
//                 }
//             }
//         }
//     }
//     return res;
// }

vector<vector<int>> parseEquals(const string& s, int& cur) {
    auto res = term(s, cur);
    while (cur < int(s.size()) && s[cur] == '=') {
        cur++;
        auto R = term(s, cur);
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                res[i][j] = (res[i][j] == R[i][j]);
            }
        }
    }
    return res;
}

vector<vector<int>> parseAnd(const string& s, int& cur) {
    auto res = parseEquals(s, cur);
    while (cur < int(s.size()) && s[cur] == '&') {
        cur++;
        auto R = parseEquals(s, cur);
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                res[i][j] &= R[i][j];
            }
        }
    }
    return res;
}

vector<vector<int>> parseOr(const string& s, int& cur) {
    auto res = parseAnd(s, cur);
    while (cur < int(s.size()) && s[cur] == '|') {
        cur++;
        auto R = parseAnd(s, cur);
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                res[i][j] |= R[i][j];
            }
        }
    }
    return res;
}

vector<vector<int>> parseXor(const string& s, int& cur) {
    auto res = parseOr(s, cur);
    while (cur < int(s.size()) && s[cur] == '^') {
        cur++;
        auto R = parseOr(s, cur);
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                res[i][j] ^= R[i][j];
            }
        }
    }
    return res;
}

vector<vector<int>> expression(const string& s, int& cur) { return parseXor(s, cur); }

const int MAX_K = 10;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
    int n, K;
    cin >> n >> K;
    vector<int> a(n), b(n), r(n);
    vector<string> expr(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i] >> expr[i] >> r[i];
        a[i]--, b[i]--;
    }
    int last;
    cin >> last;

    vector e(n, vector(2, vector<int>(2)));
    for (int i = 0; i < n; i++) {
        int init = 0;
        e[i] = expression(expr[i], init);
    }
    {
        vector<int> na, nb, nr;
        vector<vector<vector<int>>> ne;
        set<tuple<int, int, vector<vector<int>>>> s;
        for (int i = 0; i < n; i++) {
            auto tmp = make_tuple(a[i], b[i], e[i]);
            if (s.count(tmp)) continue;
            na.emplace_back(a[i]);
            nb.emplace_back(b[i]);
            ne.emplace_back(e[i]);
            nr.emplace_back(r[i]);
            s.emplace(tmp);
        }
        swap(a, na);
        swap(b, nb);
        swap(e, ne);
        swap(r, nr);
        n = a.size();
    }

    vector f(1 << K, vector<int>(1 << K, -1));
    for (int i = 0; i < 1 << K; i++) {
        set<pair<int, int>> s;
        for (int k = 0; k < n; k++) {
            int x = i >> a[k] & 1;
            for (int d = 0; d < 2; d++) {
                if (not e[k][x][d]) continue;
                if (s.count({b[k], d})) continue;
                for (int j = 0; j < 1 << K; j++) {
                    if (f[i][j] == -1 and (j >> b[k] & 1) == d) {
                        f[i][j] = r[k];
                    }
                }
                s.emplace(b[k], d);
            }
        }
        for (int j = 0; j < 1 << K; j++) {
            if (f[i][j] == -1) {
                f[i][j] = last;
            }
        }
    }

    vector<ll> ans(3, 0);
    vector<bitset<1 << MAX_K>> F(1 << K);
    for (int i = 0; i < 1 << K; i++) {
        for (int j = 0; j < 1 << MAX_K; j++) {
            F[i][j] = 0;
        }
        for (int j = 0; j < 1 << K; j++) {
            F[i][j] = f[i][j];
        }
    }
    for (int x = 0; x < 1 << K; x++) {
        ans[0] += not(f[x][x] == 0);
        for (int y = 0; y < 1 << K; y++) {
            if (f[x][y]) {
                ans[1] += not(f[y][x] == 0);
                ans[2] += F[y].count() - (F[x] & F[y]).count();
            }
        }
    }

    cout << ans << '\n';
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3484kb

input:

3 2
1 1 (x=0)&(y=1) 1
1 1 (x=1)&(y=(x^x)) 0
2 2 (x=1)|(y=0) 0
1

output:

0 0 0

result:

ok single line: '0 0 0'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3792kb

input:

4 3
2 1 x=0&(y=1) 1
1 2 !x^!!y 0
2 3 ((x|1)=y)&1&1 1
3 1 !x&!x&!x 0
1

output:

3 25 52

result:

ok single line: '3 25 52'

Test #3:

score: 0
Accepted
time: 33ms
memory: 4908kb

input:

1413 3
1 3 0 0
3 3 !x 0
2 2 x=0 1
1 2 !y^0 1
2 3 (x^1) 0
3 2 ((!0)) 1
1 1 !!1=(y) 0
2 2 !(1^x)&y 1
3 2 (y)&1|!!1 0
3 1 !x=(y&y=y) 0
2 1 (((!1)^!x)) 1
2 3 !0=(0&y)=1&y 0
1 2 ((((!0)))|!1) 0
3 1 !(y=!1=x|(!x)) 0
1 1 ((((y=!y)))&!0) 0
2 3 ((y=1)^!1^!!1|0) 1
2 3 1|(!x)&!x|1|(x=1) 1
2 3 !0^!!!!y&0=(!1&!0...

output:

4 16 0

result:

ok single line: '4 16 0'

Test #4:

score: 0
Accepted
time: 250ms
memory: 38580kb

input:

181737 10
5 2 1 1
1 10 !1=!x 0
10 1 (1^x) 0
2 4 !1 1
10 8 y=(!1)^1 1
6 2 !((x&!x)) 1
1 10 !!((!x)|x) 1
7 10 (((0))) 0
7 3 !(1)^!x 0
10 4 (!1)&x 0
7 7 !y&!0 1
8 8 !1=(x)|1^1 1
2 6 ((!!!x)) 0
7 2 1 1
2 2 y=1=0 0
6 3 (!0) 0
6 4 0 0
1 1 (!1) 1
1 8 y 1
3 5 !x|!x^!1 0
4 7 (!0) 0
3 4 !1&1&!1|!0 1
2 7 ((0|1...

output:

1024 1048576 0

result:

ok single line: '1024 1048576 0'

Test #5:

score: 0
Accepted
time: 19ms
memory: 82372kb

input:

1 3
1 1 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!...

output:

4 16 0

result:

ok single line: '4 16 0'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3596kb

input:

1 1
1 1 x^y|1 0
1

output:

1 1 0

result:

ok single line: '1 1 0'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3796kb

input:

1 1
1 1 x&y|1 0
1

output:

0 0 0

result:

ok single line: '0 0 0'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3732kb

input:

1 1
1 1 x=y|1 0
1

output:

0 0 0

result:

ok single line: '0 0 0'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3524kb

input:

2 2
1 2 !x&!y 1
1 1 !x&y 0
1

output:

4 12 2

result:

ok single line: '4 12 2'

Test #10:

score: 0
Accepted
time: 3ms
memory: 7720kb

input:

2 10
9 8 ((((!((!x=1))^(!1&(x|x|!y))&((!y&!x=(x=y)))&!((((x=1))&(0=(y))^(!!(!!x^1=x)&(x)^y&1=!x&1=(((!0^(1)^1))^!(((((y))|x|!y))))^!!0=!y&(0)|(y=x&!y&y=x)))=((((!!y&!!0|!0^!0)=!x))))^0&(((!1=!(!x)))|(((((x=1|!y|y)=(!1^1^0^(0)))=!0^1)))=(!(!1^(((((!1)^!x^0))))=(1)^((((y=((x))|(0)|(!1^1)))|(!!!y))=((!...

output:

0 0 0

result:

ok single line: '0 0 0'

Test #11:

score: 0
Accepted
time: 0ms
memory: 3796kb

input:

4 3
1 1 !!!!!!x 0
2 1 !!y 1
1 2 !!!!!x 1
2 2 !!!x 0
1

output:

4 16 0

result:

ok single line: '4 16 0'

Test #12:

score: 0
Accepted
time: 3ms
memory: 55200kb

input:

1 1
1 1 ((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

output:

1 1 0

result:

ok single line: '1 1 0'

Test #13:

score: 0
Accepted
time: 127ms
memory: 41524kb

input:

200000 10
3 10 !x^!y 1
3 10 !x^!y 1
3 10 !x^!y 1
3 10 !x^!y 1
3 10 !x^!y 1
3 10 !x^!y 1
3 10 !x^!y 1
3 10 !x^!y 1
3 10 !x^!y 1
3 10 !x^!y 1
3 10 !x^!y 1
3 10 !x^!y 1
3 10 !x^!y 1
3 10 !x^!y 1
3 10 !x^!y 1
3 10 !x^!y 1
3 10 !x^!y 1
3 10 !x^!y 1
3 10 !x^!y 1
3 10 !x^!y 1
3 10 !x^!y 1
3 10 !x^!y 1
3 10...

output:

512 262144 134217728

result:

ok single line: '512 262144 134217728'

Test #14:

score: 0
Accepted
time: 1ms
memory: 3480kb

input:

10 3
3 1 (!x) 1
3 2 !1&x&1&!y 1
2 1 ((x)&y) 1
1 3 0 0
2 2 !1&0=y&0 1
3 3 (!y)^y 1
2 1 0|((!y)) 0
3 2 x 0
2 2 (y|1^x) 0
2 1 ((!0)|y) 0
1

output:

8 64 0

result:

ok single line: '8 64 0'

Test #15:

score: 0
Accepted
time: 0ms
memory: 3520kb

input:

0 3
1

output:

8 64 0

result:

ok single line: '8 64 0'