QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#440662#8770. ComparatorANewZhiyangfan#AC ✓792ms425124kbC++144.5kb2024-06-13 22:20:282024-06-13 22:20:28

Judging History

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

  • [2024-06-13 22:20:28]
  • 评测
  • 测评结果:AC
  • 用时:792ms
  • 内存:425124kb
  • [2024-06-13 22:20:28]
  • 提交

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'