QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#428329#8770. Comparatorucup-team1198#AC ✓636ms10692kbC++208.0kb2024-06-01 18:46:582024-06-01 18:46:58

Judging History

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

  • [2024-06-01 18:46:58]
  • 评测
  • 测评结果:AC
  • 用时:636ms
  • 内存:10692kb
  • [2024-06-01 18:46:58]
  • 提交

answer

#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;

int k;

struct Subset {
  int set_mask;
  int should;
  Subset(int set_mask, int should): set_mask(set_mask), should(should) {}
  Subset(): set_mask(0), should(0) {}
  bool operator==(const Subset& other) const = default;
  bool contains(int x) const {
    return (x & set_mask) == should;
  }
};

const Subset NONE(-1, -1);

int size(Subset S) {
  if (S == NONE)
    return 0;
  return 1 << (k - __builtin_popcount(S.set_mask));
}

Subset inter(Subset S1, Subset S2) {
  int common = S1.set_mask & S2.set_mask;
  if ((S1.should & common) != (S2.should & common))
    return NONE;
  return Subset(S1.set_mask | S2.set_mask, S1.should | S2.should);
}

const int N = (1 << 10) + 228;

vector<pair<Subset, int>> rules[N];
Subset remains[N];

struct BinFunc {
  bool vals[2][2];
  BinFunc(bool val00, bool val01, bool val10, bool val11) {
    vals[0][0] = val00;
    vals[0][1] = val01;
    vals[1][0] = val10;
    vals[1][1] = val11;
  }
  BinFunc() {}
};

BinFunc operator&(BinFunc first, BinFunc second) {
  BinFunc ans;
  for (int i = 0; i < 2; ++i) {
    for (int j = 0; j < 2; ++j)
      ans.vals[i][j] = first.vals[i][j] & second.vals[i][j];
  }
  return ans;
}

BinFunc operator|(BinFunc first, BinFunc second) {
  BinFunc ans;
  for (int i = 0; i < 2; ++i) {
    for (int j = 0; j < 2; ++j)
      ans.vals[i][j] = first.vals[i][j] | second.vals[i][j];
  }
  return ans;
}

BinFunc operator^(BinFunc first, BinFunc second) {
  BinFunc ans;
  for (int i = 0; i < 2; ++i) {
    for (int j = 0; j < 2; ++j)
      ans.vals[i][j] = first.vals[i][j] ^ second.vals[i][j];
  }
  return ans;
}

BinFunc eq(BinFunc first, BinFunc second) {
  BinFunc ans;
  for (int i = 0; i < 2; ++i) {
    for (int j = 0; j < 2; ++j)
      ans.vals[i][j] = first.vals[i][j] == second.vals[i][j];
  }
  return ans;
}

BinFunc operator!(BinFunc first) {
  BinFunc ans;
  for (int i = 0; i < 2; ++i) {
    for (int j = 0; j < 2; ++j)
      ans.vals[i][j] = !first.vals[i][j];
  }
  return ans;
}

BinFunc call_op(BinFunc first, char op, BinFunc second) {
  if (op == '&')
    return first & second;
  if (op == '|')
    return first | second;
  if (op == '^')
    return first ^ second;
  if (op == '=')
    return eq(first, second);
  assert(false);
  return BinFunc();
}

int get_precedence(char c) {
  if (c == '=')
    return 0;
  if (c == '&')
    return 1;
  if (c == '|')
    return 2;
  return 3;
}

BinFunc calc_func(vector<pair<char, BinFunc>> A) {
  int n = (A.size() + 1) / 2;
  // 0, 2, 4, ... 2n-2 are funcs
  // 1, 3, 5 ... 2n-3 are ops
  vector<int> ops_order;
  vector<int> couple(2 * n - 1);
  for (int i = 1; i < 2 * n - 1; i += 2)
    ops_order.emplace_back(i);
  stable_sort(ops_order.begin(), ops_order.end(), [&](int a, int b) {
    return get_precedence(A[a].first) < get_precedence(A[b].first);
  });
  for (int i = 0; i < 2 * n - 1; i += 2)
    couple[i] = i;
  for (int j : ops_order) {
    int l1 = j - 1;
    int l2 = couple[l1];
    int r1 = j + 1;
    int r2 = couple[r1];
    BinFunc func = call_op(A[l1].second, A[j].first, A[r1].second);
    A[l2].second = func;
    A[r2].second = func;
    couple[l2] = r2;
    couple[r2] = l2;
  }
  return A[0].second;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);

  int n;
  cin >> n >> k;

  map<char, BinFunc> basic_func;
  basic_func['x'] = BinFunc(0, 0, 1, 1);
  basic_func['y'] = BinFunc(0, 1, 0, 1);
  basic_func['0'] = BinFunc(0, 0, 0, 0);
  basic_func['1'] = BinFunc(1, 1, 1, 1);

  vector<string> examples = {"x", "y", "!x", "!y", "x|y", "x&y|1", "x&y|x", "x&!x", "x=y", "(x=0)&(y=1)"};

  //for (int t = 0; t < 100000; ++t) {

  for (int left = 0; left < (1 << k); ++left) {
    rules[left].clear();
    remains[left] = Subset(0, 0);
  }

  for (int i = 0; i < n; ++i) {
    int a = rand() % k, b = rand() % k;
    string s; // = examples[rand() % examples.size()];
    int r = rand() % 2;
    cin >> a >> b;
    --a;
    --b;
    cin >> s;
    s = '(' + s + ')';
    cin >> r;
    vector<pair<char, BinFunc>> stack;
    auto try_emplace_func = [&](BinFunc func) {
      while (true) {
        if (stack.empty() || stack.back().first == '(')
          break;
        assert(stack.back().first != '\0');
        if (stack.back().first == '!') {
          func = !func;
          stack.pop_back();
        } else {
          break;
        }
      }
      stack.emplace_back('\0', func);
    };
    for (char c : s) {
      if (c == 'x' || c == 'y' || c == '0' || c == '1') {
        try_emplace_func(basic_func[c]);
      } else if (c == '=' || c == '&' || c == '|' || c == '^' || c == '!') {
        stack.emplace_back(c, BinFunc());
      } else if (c == '(') {
        stack.emplace_back('(', BinFunc());
      } else {
        // )
        assert(!stack.empty() && stack.back().first == '\0');
        int i = int(stack.size()) - 1;
        while (stack[i].first != '(')
          --i;
        vector<pair<char, BinFunc>> tmp;
        for (int j = i + 1; j < stack.size(); ++j)
          tmp.emplace_back(stack[j]);
        stack.resize(i);
        try_emplace_func(calc_func(tmp));
      }
    }
    assert(stack.size() == 1);
    assert(stack.back().first == '\0');
    BinFunc real_func = stack.back().second;
    for (int x = 0; x < 2; ++x) {
      Subset cur;
      Subset extra;
      if (real_func.vals[x][0] && real_func.vals[x][1]) {
        cur = Subset(0, 0); // everything
        extra = NONE;
      } else if (real_func.vals[x][0]) {
        cur = Subset(1 << b, 0);
        extra = Subset(1 << b, 1 << b);
      } else if (real_func.vals[x][1]) {
        cur = Subset(1 << b, 1 << b);
        extra = Subset(1 << b, 0);
      } else {
        continue;
      }
      for (int mask = 0; mask < (1 << k); ++mask) {
        int kek = (mask >> a) & 1;
        if (kek != x)
          continue;
        if (remains[mask] == NONE)
          continue;
        Subset tmp = inter(remains[mask], cur);
        if (tmp == NONE)
          continue;
        if (tmp == remains[mask]) {
          rules[mask].emplace_back(tmp, r);
          remains[mask] = NONE;
        } else {
          rules[mask].emplace_back(tmp, r);
          remains[mask] = inter(remains[mask], extra);
        }
      }
    }
  }
  int total_r;
  cin >> total_r;
  for (int i = 0; i < (1 << k); ++i) {
    if (remains[i] != NONE)
      rules[i].emplace_back(remains[i], total_r);
  }

  auto get_ans = [&](int x, int y) {
    for (auto& [S, r] : rules[x]) {
      if (S.contains(y))
        return r;
    }
    assert(false);
    return total_r;
  };
  
  int refl_errors = 0;
  for (int x = 0; x < (1 << k); ++x) {
    refl_errors += get_ans(x, x);
  }
  cout << refl_errors << ' ';

  int symm_errors = 0;
  for (int x = 0; x < (1 << k); ++x) {
    for (int y = 0; y < (1 << k); ++y) {
      symm_errors += get_ans(x, y) && get_ans(y, x);
    }
  }
  cout << symm_errors << ' ';

  int tr_errors = 0;
  for (int x = 0; x < (1 << k); ++x) {
    for (int y = 0; y < (1 << k); ++y) {
      if (!get_ans(x, y))
        continue;
      // need y < z, but not x < z
      for (auto& [S1, r1] : rules[x]) {
        for (auto& [S2, r2] : rules[y]) {
          if (r1 == 0 && r2 == 1)
            tr_errors += size(inter(S1, S2));
        }
      }
    }
  }
  cout << tr_errors << '\n';


  /*int dumb_tr = 0;
  for (int x = 0; x < (1 << k); ++x) {
    for (int y = 0; y < (1 << k); ++y) {
      for (int z = 0; z < (1 << k); ++z)
        dumb_tr += get_ans(x, y) && get_ans(y, z) && !get_ans(x, z);
    }
  }
  assert(tr_errors == dumb_tr);

  }*/
  return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3840kb

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: 3648kb

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: 41ms
memory: 3640kb

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: 369ms
memory: 3664kb

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: 9ms
memory: 10692kb

input:

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

output:

4 16 0

result:

ok single line: '4 16 0'

Test #6:

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

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: 3672kb

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: 3876kb

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: 3672kb

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

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: 0ms
memory: 3580kb

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

input:

1 1
1 1 ((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

output:

1 1 0

result:

ok single line: '1 1 0'

Test #13:

score: 0
Accepted
time: 636ms
memory: 3704kb

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: 0ms
memory: 3560kb

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: 0ms
memory: 3876kb

input:

0 3
1

output:

8 64 0

result:

ok single line: '8 64 0'