QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#528647#8770. ComparatorLittleCubeAC ✓305ms8196kbC++174.3kb2024-08-23 18:28:372024-08-23 18:28:38

Judging History

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

  • [2024-08-23 18:28:38]
  • 评测
  • 测评结果：AC
  • 用时：305ms
  • 内存：8196kb
查看
  • [2024-08-23 18:28:37]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<double, double>
#define F first
#define S second
#define all(x) x.begin(), x.end()
using namespace std;

int pri(char c)
{
    switch(c)
    {
        case '=':
        return 1;
        case '&':
        return 2;
        case '|':
        return 3;
        case '^':
        return 4;
        case ')':
        return 5;
        case '(':
        return 6;
    }
    return 0;
}

int eval(string s, int x, int y)
{
    vector<int> res;
    vector<char> ops;
    s = "(" + s + ")";
    for (auto c : s)
    {
        if ("xy01"s.find(c) != string::npos)
        {
            if (c == 'x')
                res.emplace_back(x);
            else if (c == 'y')
                res.emplace_back(y);
            else if (c == '0')
                res.emplace_back(0);
            else if (c == '1')
                res.emplace_back(1);
            while (ops.back() == '!')
                res.back() = !res.back(), ops.pop_back();
        }
        else if (c == '(')
            ops.emplace_back('(');
        else if ("=&|^)"s.find(c) != string::npos)
        {
            while (pri(ops.back()) <= pri(c))
            {
                int b = res.back(); res.pop_back();
                int a = res.back(); res.pop_back();
                if (ops.back() == '=')
                    res.emplace_back(a == b);
                else if (ops.back() == '&')
                    res.emplace_back(a && b);
                else if (ops.back() == '^')
                    res.emplace_back(a ^ b);
                else if (ops.back() == '|')
                    res.emplace_back(a || b);
                ops.pop_back();
            }
            if (c == ')') 
            {
                ops.pop_back(); // (
                while (!ops.empty() && ops.back() == '!')
                    res.back() = !res.back(), ops.pop_back();
            }
            else ops.emplace_back(c);
        }
        else if (c == '!')
            ops.emplace_back('!');
    }
    return res.back();
}

int N, K;
pii rule[10][10][2][2], res[1024][10][2];
bitset<1024> G[1024];

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> N >> K;
    for (int i = 0; i < K; i++)
        for (int j = 0; j < K; j++)
            for (int x = 0; x <= 1; x++)
                for (int y = 0; y <= 1; y++)
                    rule[i][j][x][y] = pii(N + 2, -1);
    for (int i = 1; i <= N; i++)
    {
        int a, b, ret;
        string s;
        cin >> a >> b >> s >> ret;
        a--, b--;
        for (int x = 0; x <= 1; x++)
            for (int y = 0; y <= 1; y++)
                if (eval(s, x, y))
                    rule[a][b][x][y] = min(rule[a][b][x][y], pii(i, ret));
    }
    int def;
    cin >> def;
    for (int i = 0; i < K; i++)
        for (int j = 0; j < K; j++)
            for (int x = 0; x <= 1; x++)
                for (int y = 0; y <= 1; y++)
                    rule[i][j][x][y] = min(rule[i][j][x][y], pii(N + 1, def));
    
    for (int i = 0; i < (1 << K); i++)
        for (int j = 0; j < K; j++)
            for (int y = 0; y <= 1; y++)
            {
                res[i][j][y] = pii(N + 1, def);
                for (int k = 0; k < K; k++)
                    res[i][j][y] = min(res[i][j][y], rule[k][j][(i >> k) & 1][y]);
            }
    
    for (int i = 0; i < (1 << K); i++)
        for (int j = 0; j < (1 << K); j++)
        {   
            pii ret = pii(N + 1, def); 
            for (int k = 0; k < K; k++)
                ret = min(ret, res[i][k][(j >> k) & 1]);
            G[i][j] = (ret.S != 0);
        }


    int bad = 0;
    for (int i = 0; i < (1 << K); i++)
        if (G[i][i]) bad++;
    cout << bad << ' ';

    bad = 0;
    for (int i = 0; i < (1 << K); i++)
        for (int j = 0; j < (1 << K); j++)
            if (G[i][j] && G[j][i]) bad++;
    cout << bad << ' ';


    bad = 0;
    for (int i = 0; i < (1 << K); i++)
        for (int j = 0; j < (1 << K); j++)
            if (G[i][j]) 
                bad += (G[j] & (~G[i])).count();
    cout << bad << '\n';
}

/*
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
*/
源文件, 语言: C++17

詳細信息

Test #1:

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

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: 3572kb

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: 114ms
memory: 3688kb

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: 305ms
memory: 3916kb

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: 94ms
memory: 8196kb

input:

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

output:

4 16 0

result:

ok single line: '4 16 0'

Test #6:

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

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: 3868kb

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: 3864kb

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: 3608kb

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: 25ms
memory: 4024kb

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: 3572kb

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: 11ms
memory: 4008kb

input:

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

output:

1 1 0

result:

ok single line: '1 1 0'

Test #13:

score: 0
Accepted
time: 260ms
memory: 3920kb

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: 0ms
memory: 3572kb

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: 3832kb

input:

0 3
1

output:

8 64 0

result:

ok single line: '8 64 0'
English 繁體中文 简体中文

伺服器時間: 2024-12-05 10:58:37 | 開源專案