QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#743823#8770. Comparatorydzr00000WA 617ms12344kbC++176.8kb2024-11-13 20:07:122024-11-13 20:07:12

Judging History

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

  • [2024-11-13 20:07:12]
  • 评测
  • 测评结果:WA
  • 用时:617ms
  • 内存:12344kb
  • [2024-11-13 20:07:12]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
template<typename T>
class Stack{
    private:
        T stk[1000001];
        int stktop=0;
    public:
        inline bool empty(){return !stktop;}
        inline int size(){return stktop;}
        inline T top(){if(!stktop) assert(false);return stk[stktop];}
        inline void push(const T &x){stk[++stktop]=x;}
        inline void pop(){if(stktop<0) assert(false);stktop--;}
};
class Expression{
    private:
        inline bool check_operator(char c)
        {
            return c=='&'||c=='|'||c=='!'||c=='='||c=='^';
        }
        inline int operator_num(char c)
        {
            if(c=='&'||c=='|'||c=='='||c=='^')
                return 1;
            if(c=='!')
                return 2;
            return 3;
        }
        Stack<char>fix;
        Stack<char>formula;
        Stack<char>num;
        Stack<char>st;
        inline void postfix(string s)
        {
            s=s+'@';
            for(int i=0;i<s.length();i++)
            {
                if(s[i]=='(')
                    st.push(s[i]);
                else if(s[i]==')')
                {
                    while(st.top()!='(')
                    {
                        fix.push(st.top());
                        st.pop();
                    }
                    st.pop();
                }
                else if(check_operator(s[i]))
                {
                    if(s[i]=='!')
                    {
                        int j=i,cnt=0;
                        while(j<s.length()&&s[j]=='!')
                            cnt++,j++;
                        if(cnt>1)
                        {
                            if(cnt&1)
                                i=j-2;
                            else
                                i=j-1;
                            continue;
                        }
                    }
                    while(!st.empty()&&st.top()!='('&&operator_num(st.top())>=operator_num(s[i]))
                    {
                        fix.push(st.top());
                        st.pop();
                    }
                    st.push(s[i]);
                }
                else if(s[i]=='0'||s[i]=='1')
                    fix.push(s[i]);
                else
                {
                    while(!st.empty())
                    {
                        fix.push(st.top());
                        st.pop();
                    }
                }
            }
        }
        inline void reverse_stack()
        {
            while(!fix.empty())
            {
                formula.push(fix.top());
                fix.pop();
            }
        }
        inline bool GetVal(const char &c)
        {
            return c=='1';
        }
        inline char GetChar(const bool &f)
        {
            return f?'1':'0';
        }
        inline char calculate()
        {
            while(!formula.empty())
            {
                char now=formula.top();
                formula.pop();
                if(!check_operator(now))
                    num.push(now);
                else
                {
                    if(now=='&')
                    {
                        bool a=GetVal(num.top());
                        num.pop();
                        bool b=GetVal(num.top());
                        num.pop();
                        num.push(GetChar(a&b));
                    }
                    else if(now=='|')
                    {
                        bool a=GetVal(num.top());
                        num.pop();
                        bool b=GetVal(num.top());
                        num.pop();
                        num.push(GetChar(a|b));
                    }
                    else if(now=='!')
                    {
                        bool a=GetVal(num.top());
                        num.pop();
                        num.push(GetChar(!a));
                    }
                    else if(now=='^')
                    {
                        bool a=GetVal(num.top());
                        num.pop();
                        bool b=GetVal(num.top());
                        num.pop();
                        num.push(GetChar(a^b));
                    }
                    else
                    {
                        bool a=GetVal(num.top());
                        num.pop();
                        bool b=GetVal(num.top());
                        num.pop();
                        num.push(GetChar(a==b));
                    }
                }
            }
            char ans=num.top();
            num.pop();
            return ans;
        }
    public:
        inline bool work(const string &expr)
        {
            postfix(expr);
            reverse_stack();
            return calculate()=='1';
        }
};
Expression E;
struct Lim{
    int a,x,b,y,r;
};
vector<Lim>L;
bool vis[11][2][11][2];
int res[1<<10][1<<10];
bitset<1024>f[1<<10],g[1<<10];
int main(){
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        int a,b,r;
        string expr;
        cin>>a>>b>>expr>>r;
        for(int x: {0,1})
            for(int y: {0,1})
            {
                string upd=expr;
                for(auto &ch: upd)
                {
                    if(ch=='x')
                        ch=(char)(x+'0');
                    if(ch=='y')
                        ch=(char)(y+'0');
                }
                if(E.work(upd))
                {
                    if(!vis[a][x][b][y])
                        L.push_back({a,x,b,y,r});
                    vis[a][x][b][y]=true;
                }
            }
    }
    memset(res,-1,sizeof(res));
    for(auto [a,x,b,y,r]: L)
    {
        for(int s=0;s<(1<<k);s++)
            for(int t=0;t<(1<<k);t++)
            {
                int g=((s>>(a-1))&1);
                int h=((t>>(b-1))&1);
                if(g==x&&h==y&&res[s][t]==-1)
                    res[s][t]=r;
            }
    }
    int z;
    cin>>z;
    for(int i=0;i<(1<<k);i++)
        for(int j=0;j<(1<<k);j++)
            if(res[i][j]==-1)
                res[i][j]=z;
    int vRefl=0,vSym=0,vTrans=0;
    for(int i=0;i<(1<<k);i++)
        if(res[i][i])
            vRefl++;
    for(int i=0;i<(1<<k);i++)
        for(int j=0;j<(1<<k);j++)
            if(res[i][j]&&res[j][i])
                vSym++;
    for(int i=0;i<(1<<k);i++)
        for(int j=0;j<(1<<k);j++)
            if(res[i][j])
            {
                f[i][j]=1;
                g[j][i]=1;
            }
    for(int i=0;i<(1<<k);i++)
        for(int j=0;j<(1<<k);j++)
            if(!res[i][j])
                vTrans+=(f[i]&g[j]).count();
    cout<<vRefl<<" "<<vSym<<" "<<vTrans<<endl;
    
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 11028kb

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: 2ms
memory: 11768kb

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: 57ms
memory: 11380kb

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: 617ms
memory: 10024kb

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: 21ms
memory: 12344kb

input:

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

output:

4 16 0

result:

ok single line: '4 16 0'

Test #6:

score: -100
Wrong Answer
time: 0ms
memory: 11288kb

input:

1 1
1 1 x^y|1 0
1

output:

0 0 0

result:

wrong answer 1st lines differ - expected: '1 1 0', found: '0 0 0'