QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#440662 | #8770. Comparator | ANewZhiyangfan# | AC ✓ | 792ms | 425124kb | C++14 | 4.5kb | 2024-06-13 22:20:28 | 2024-06-13 22:20:28 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int prio(char c){
if(c=='^') return 2;
if(c=='|') return 3;
if(c=='&') return 4;
if(c=='=') return 5;
if(c=='!') return 6;
return 7;
}
const int N=1024;
int n,k;
int solve(const string &str,int x,int y){
//cerr<<"solve "<<str<<' '<<x<<' '<<y<<' ';
vector<char> stk;
vector<int> seq;
for(int i=0; i<str.size(); i++){
char c=str[i];
if(c=='0'||c=='1'){
seq.emplace_back(c=='0'?0:1);
continue;
}
if(c=='x'||c=='y'){
seq.emplace_back(c=='x'?x:y);
continue;
}
if(c=='!'){
assert(i+1<str.size());
if(str[i+1]=='!'){
i=i+1;
continue;
}
if(str[i+1]=='x'||str[i+1]=='y')seq.emplace_back(str[i+1]=='x'?x:y);
else seq.emplace_back(str[i+1]-'0');
seq.emplace_back(prio(c));
i=i+1;
continue;
}
while(stk.size()&&prio(stk.back())>=prio(c)){
seq.emplace_back(prio(stk.back()));
stk.pop_back();
}
stk.emplace_back(c);
}
while(stk.size()) seq.emplace_back(prio(stk.back())),stk.pop_back();
//for(auto p:seq) cerr<<p<<' ';
//cerr<<endl;
vector<int> S;
for(auto p:seq){
if(p<=1){
S.emplace_back(p);
continue;
}
if(p==2){
int u=S[S.size()-1],v=S[S.size()-2];
S.pop_back(),S.pop_back();
S.emplace_back(v^u);
}
if(p==3){
int u=S[S.size()-1],v=S[S.size()-2];
S.pop_back(),S.pop_back();
S.emplace_back(v|u);
}
if(p==4){
int u=S[S.size()-1],v=S[S.size()-2];
S.pop_back(),S.pop_back();
S.emplace_back(v&u);
}
if(p==5){
int u=S[S.size()-1],v=S[S.size()-2];
S.pop_back(),S.pop_back();
S.emplace_back(v==u);
}
if(p==6){
int u=S[S.size()-1];
S.pop_back();
S.emplace_back(!u);
}
assert(p!=7);
}
assert(S.size()==1);
//cerr<<S.back()<<endl;
return S.back();
}
int calcu(const string &str,int x,int y){
vector<char> stk;
for(auto c:str){
if(c==')'){
string now;
while(stk.size()&&stk.back()!='('){
now+=stk.back();
stk.pop_back();
}
assert(stk.size());
stk.pop_back();
reverse(now.begin(),now.end());
stk.emplace_back(solve(now,x,y)+'0');
}
else{
stk.emplace_back(c);
}
}
string now;
for(auto c:stk) now+=c;
return solve(now,x,y);
}
int main(){
cin.tie(0),cout.tie(0)->sync_with_stdio(false);
cin>>n>>k;
vector<bitset<N>> ver(1<<k),del(1<<k);
vector<vector<array<array<vector<int>,2>,2>>> rec(k,vector<array<array<vector<int>,2>,2>>(k));
for(int i=0; i<(1<<k); i++){
for(int j=0; j<(1<<k); j++){
for(int p=0; p<k; p++){
for(int q=0; q<k; q++){
rec[p][q][i>>p&1][j>>q&1].emplace_back((i<<k)+j);
}
}
}
}
//vector<bitset<N>> chk(1<<k),Del(1<<k);
for(int t=0; t<n; t++){
int X,Y,v;
string expr;
cin>>X>>Y>>expr>>v;
X--,Y--;
for(int x:{0,1}){
for(int y:{0,1}){
int t=calcu(expr,x,y);
if(!t) continue;
for(auto msk:rec[X][Y][x][y]){
int a=(msk>>k),b=msk-(a<<k);
if(del[a][b]) continue;
del[a][b]=1;
ver[a][b]=v;
}
rec[X][Y][x][y].clear();
}
}/*
for(int i=0; i<(1<<k); i++){
for(int j=0; j<(1<<k); j++){
if(Del[i][j]) continue;
int t=calcu(expr,i>>X&1,j>>Y&1);
if(t){
Del[i][j]=1;
chk[i][j]=v;
}
}
}*/
}
int u;
cin>>u;
for(int i=0; i<(1<<k); i++){
for(int j=0; j<(1<<k); j++){
//if(!Del[i][j]) chk[i][j]=u;
if(del[i][j]) continue;
ver[i][j]=u;
}
}
long long ans=0;
for(int i=0; i<(1<<k); i++){
if(ver[i][i]) ans++;
}
cout<<ans<<' ';
ans=0;
for(int i=0; i<(1<<k); i++){
for(int j=0; j<(1<<k); j++){
if(ver[i][j]&&ver[j][i]){
ans++;
}
}
}
cout<<ans<<' ';
ans=0;
for(int i=0; i<(1<<k); i++){
for(int j=0; j<(1<<k); j++){
if(!ver[i][j]) continue;
ans+=(ver[j].count()-(ver[j]&ver[i]).count());
}
}
cout<<ans<<endl;
/*
for(int i=0; i<(1<<k); i++){
for(int j=0; j<(1<<k); j++){
cerr<<ver[i][j];
}
cerr<<endl;
}
cerr<<endl;
for(int i=0; i<(1<<k); i++){
for(int j=0; j<(1<<k); j++){
cerr<<chk[i][j];
}
cerr<<endl;
}*/
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3616kb
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: 1ms
memory: 3624kb
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: 112ms
memory: 3840kb
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: 792ms
memory: 425124kb
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: 11ms
memory: 8136kb
input:
1 3 1 1 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!...
output:
4 16 0
result:
ok single line: '4 16 0'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3560kb
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: 3536kb
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: 1ms
memory: 3596kb
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: 3536kb
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: 409ms
memory: 425004kb
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: 1ms
memory: 3584kb
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: 16ms
memory: 3788kb
input:
1 1 1 1 ((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...
output:
1 1 0
result:
ok single line: '1 1 0'
Test #13:
score: 0
Accepted
time: 616ms
memory: 424988kb
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: 3628kb
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: 1ms
memory: 3552kb
input:
0 3 1
output:
8 64 0
result:
ok single line: '8 64 0'