UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#210639#3785. 恒真zhuangmingyi1002ms1216kbC++111.5kb2024-08-07 08:56:022024-08-07 12:01:42

answer

#include <bits/stdc++.h>
using namespace std;
int t[27], cnt, n;
bool b[9], ans = 1;
char c[9], s[1005];
stack<bool> stk;
void dfs(int step)
{
    if (step == cnt + 1)
    {
        for (int i = 1; i <= n; ++i)
        {
            if ('a' <= s[i] && s[i] <= 'z') stk.push(b[t[s[i] - 'a' + 1]]);
            if (s[i] == '!')
            {
                int a = stk.top();
                stk.pop();
                stk.push(!a);
            }
            if (s[i] == '&')
            {
                int a = stk.top();
                stk.pop();
                int b = stk.top();
                stk.pop();
                stk.push(a & b);
            }
            if (s[i] == '|')
            {
                int a = stk.top();
                stk.pop();
                int b = stk.top();
                stk.pop();
                stk.push(a | b);
            }
            if (s[i] == '^')
            {
                int a = stk.top();
                stk.pop();
                int b = stk.top();
                stk.pop();
                stk.push(a ^ b);
            }
        }
        ans &= stk.top();
        stk.pop();
        return;
    }
    b[step] = 1;
    dfs(step + 1);
    b[step] = 0;
    dfs(step + 1);
}
int main()
{
    while (cin >> s[n + 1])
    {
        n++;
        if ('a' <= s[n] && s[n] <= 'z' && !t[s[n] - 'a' + 1]) c[++cnt] = s[n], t[s[n] - 'a' + 1] = cnt;
    }
    dfs(1);
    cout << (ans ? "YES" : "NO") << endl;
    return 0;
}

Details

小提示:点击横条可展开更详细的信息

Subtask #1:

score: 30
Accepted

Test #1:

score: 30
Accepted
time: 0ms
memory: 1212kb

input:

a a | a b & |

output:

NO

result:

ok "NO"

Test #2:

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

input:

a b | a b | & a b | a b | & &

output:

NO

result:

ok "NO"

Test #3:

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

input:

a b | c d | & e f | g h | & &

output:

NO

result:

ok "NO"

Test #4:

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

input:

c d |

output:

NO

result:

ok "NO"

Test #5:

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

input:

a a & b & b a & b b & & | b b | b b | & b b a & | | | b b & a a & & b a | a a | & & b a a | | a a & ...

output:

NO

result:

ok "NO"

Test #6:

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

input:

b a b | | b d & c b & & & d d | a | d c & b b & | & & c c & d & d a & d a & & | b & & a c & b b | | ...

output:

NO

result:

ok "NO"

Test #7:

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

input:

g d | f a & | h a & a a & | & d a e & e g & & | & b e & a a | & g f & h a & & & h e | f g | | e c & ...

output:

NO

result:

ok "NO"

Test #8:

score: 0
Accepted
time: 2ms
memory: 1216kb

input:

c b & a a | | g g h | & | a e | g b & | f f | c c & & & | b c b | f b | | | b e | f | b d & c a & | ...

output:

NO

result:

ok "NO"

Subtask #2:

score: 30
Accepted

Test #9:

score: 30
Accepted
time: 0ms
memory: 1216kb

input:

a a & a ! & a a | a a | & & ! a a a | & a a | a | | a a | a a & | ! | | a ! ! ! ! a a | a ! & ! ! | ...

output:

YES

result:

ok "YES"

Test #10:

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

input:

a ! ! a a | a a & & | a a ! | a a & ! & & ! ! a ! ! a & a ! ! a a & a ! | | & a a & a a & | a a | ! ...

output:

NO

result:

ok "NO"

Test #11:

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

input:

a ! ! a a | a a & & | a a ! | a a & ! & & ! ! a ! ! a & a ! ! a a & a ! | | & a a & a a & | a a | ! ...

output:

NO

result:

ok "NO"

Test #12:

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

input:

a a a | ! | a & a a a | ! & a | | a a & ! a a & a a | | & ! a a a & | a a | a | & a a | a a | | a ! ...

output:

YES

result:

ok "YES"

Test #13:

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

input:

a a ! a a | ^ a a | a a | ^ | a a | a ^ a ! a ! | ^ | ! | a a a | ! & a ! a | a a ^ a a ^ & | ^ a ^ ...

output:

NO

result:

ok "NO"

Test #14:

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

input:

a a a a | a a | | a a | a a | ^ & ! a a | ! a a | a & | a | & & a a & a a ^ & a a | a ! | ^ a a & ! ...

output:

NO

result:

ok "NO"

Test #15:

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

input:

a a ! a a ^ ^ a ! | | a a | a a | ^ a a | ! | a a | a a | | a a | a | ^ | | a | a a | a a | | a ! a ...

output:

YES

result:

ok "YES"

Subtask #3:

score: 40
Accepted

Test #16:

score: 40
Accepted
time: 0ms
memory: 1216kb

input:

a b | a ! b ! | |

output:

YES

result:

ok "YES"

Test #17:

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

input:

a b ! | a ! b | &

output:

NO

result:

ok "NO"

Test #18:

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

input:

a b ! | a ! b | |

output:

YES

result:

ok "YES"

Test #19:

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

input:

a b | c ! | a ! b | c | | a b ! c | | |

output:

YES

result:

ok "YES"

Test #20:

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

input:

c b b | | b b | c c | | | c ! c b | ^ ! ^ b c | b c | | c c | ! ^ b ! | | a a | b a | | b b | ! | ! ...

output:

NO

result:

ok "NO"

Test #21:

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

input:

b a | a a | ^ b | b a a & | ! | b ! c a ^ | ! a ^ | c ! ! b b | ! ^ c b | a | b & | b a | ! c c | a ...

output:

NO

result:

ok "NO"

Test #22:

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

input:

b ! b | c a c | ! | ! a c | b c | | ! b c a | c a | | | | ^ b c | c ! & a c & c c | | | c a | ! a ! ...

output:

YES

result:

ok "YES"

Test #23:

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

input:

d c c | ! c ! c ! | | | ! c a | d ! | c b | a d | | | d c ^ ! c c | ! | | b b | b | b a | ! | b b b ...

output:

NO

result:

ok "NO"

Test #24:

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

input:

b ! c ! d d | | d c ^ d d | | | ! d a | ! ! ! | c a c | d ! | ^ ! c a | c d | | a c | d c | ^ | b c ...

output:

NO

result:

ok "NO"

Test #25:

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

input:

b ! g ! h d | | d g ^ h d | | | ! d e | ! ! ! | g e c | h ! | ^ ! g e | c d | | e c | h c | ^ | b g ...

output:

NO

result:

ok "NO"

Test #26:

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

input:

b ! g ! h d | | d g ^ h d | | | ! d e | ! ! ! | g ! ! d ! ! h c | d ^ ! | | | c ! g e | | ! ! b b g ...

output:

NO

result:

ok "NO"

Test #27:

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

input:

a ! b | c | d | a b ! | c | d | | a b | c ! | d | | a b | c | d ! | |

output:

YES

result:

ok "YES"

Test #28:

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

input:

a a ! | b b ! | & c c ! | d d ! | & & e e ! | f f ! | & & g ! g | h ! h | & &

output:

YES

result:

ok "YES"

Extra Test:

score: 0
Extra Test Passed