QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #743624 | #8770. Comparator | ydzr00000 | RE | 2ms | 7668kb | C++17 | 6.0kb | 2024-11-13 19:40:20 | 2024-11-13 19:40:20 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
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 3;
return 2;
}
stack<char>fix;
stack<char>formula;
stack<char>num;
inline void postfix(string s)
{
s=s+'@';
stack<char>st;
for(int i=0;i<s.length();i++)
{
if(s[i]==' ')
continue;
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]))
{
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 if(s[i]=='@')
{
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: 7660kb
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: 7668kb
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: -100
Runtime Error
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...