QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#436698 | #8770. Comparator | mendicillin2 | WA | 0ms | 3564kb | C++20 | 4.3kb | 2024-06-09 02:43:54 | 2024-06-09 02:43:54 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;
const string BINOPS = "^|&=";
int op(int p, int x, int y) {
if (p == 0) return x ^ y;
else if (p == 1) return x | y;
else if (p == 2) return x & y;
else if (p == 3) return x == y;
assert(false);
}
int evaluate(string expr, int x, int y) {
expr.push_back(char(0));
int cur = 0;
auto evaluate = [&](auto&& self, int p) -> int {
if (p < 4) {
// p-th binary operator
int res = self(self, p+1);
while (expr[cur] == BINOPS[p]) {
cur++;
auto rres = self(self, p+1);
res = op(p, res, rres);
}
return res;
} else if (p == 4) {
char c = expr[cur++];
if (c == 'x') {
return x;
} else if (c == 'y') {
return y;
} else if (c == '0') {
return 0;
} else if (c == '1') {
return 1;
} else if (c == '!') {
return !self(self, 4);
} else if (c == '(') {
int res = self(self, 0);
return res;
} else {
cerr << "Unexpected character: " << c << endl;
assert(false);
}
} else assert(false);
};
return evaluate(evaluate, 0);
}
constexpr bool DEBUG = false;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(20);
if constexpr (DEBUG) {
for (int x = 0; x < 2; x++) {
for (int y = 0; y < 2; y++) {
assert(evaluate("(x=0)&(y=1)", x, y) == ((x==0)&&(y==1)));
assert(evaluate("(x=1)&(y=(x^x))", x, y) == ((x==1)&&(y==(x^x))));
assert(evaluate("(x=1)|(y=0)", x, y) == ((x==1)||(y==0)));
assert(evaluate("x=0&(y=1)", x, y) == ((x==0)&&(y==1)));
assert(evaluate("!x^!!y", x, y) == ((!x)^y));
assert(evaluate("((x|1)=y)&1&1", x, y) == y);
assert(evaluate("!x&!x&!x", x, y) == (!x));
}
}
cerr << "Unit tests passed" << endl;
}
int N, K;
cin >> N >> K;
using Comb = array<int, 4>; // (a, b, x, y)
auto encode = [&](int a, int b, int x, int y) -> int {
return a * (K*2*2)
+ b * (2*2)
+ x * 2
+ y;
};
V<bool> seen(K*K*2*2, false);
V<pair<Comb, int>> interesting;
for (int i = 0; i < N; i++) {
int a, b, r;
string expr;
cin >> a >> b >> expr >> r;
a--, b--;
for (int x = 0; x < 2; x++) {
for (int y = 0; y < 2; y++) {
if (evaluate(expr, x, y) == 1) {
int e = encode(a, b, x, y);
if (!seen[e]) {
seen[e] = true;
interesting.emplace_back(Comb{a, b, x, y}, r);
}
}
}
}
}
int R_end;
cin >> R_end;
auto compute_f = [&](int x, int y) -> int {
for (const auto& [inp, r] : interesting) {
const auto& [a, b, dx, dy] = inp;
if (((x >> a) & 1) == dx && ((y >> b) & 1) == dy) {
return r;
}
}
return R_end;
};
using Bitset = bitset<1 << 10>;
const int M = 1 << K;
V<Bitset> fxy(M);
V<Bitset> fyx(M);
for (int x = 0; x < M; x++) {
for (int y = 0; y < M; y++) {
auto f = compute_f(x, y);
fxy[x][y] = f;
fyx[y][x] = f;
}
}
cout << [&]() -> int {
return ranges::count_if(ranges::iota_view{0, M}, [&](int x) -> bool {
return fxy[x][x];
});
}() << ' ' << [&]() -> int {
int cnt = 0;
for (int x = 0; x < M; x++) {
for (int y = 0; y < M; y++) {
cnt += (fxy[x][y] && fxy[y][x]);
}
}
return cnt;
}() << ' ' << [&]() -> int {
int cnt = 0;
for (int x = 0; x < M; x++) {
for (int z = 0; z < M; z++) {
if (!fxy[x][z]) {
cnt += int((fxy[x] & fyx[z]).count());
}
}
}
return cnt;
}() << '\n';
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3564kb
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:
2 4 0
result:
wrong answer 1st lines differ - expected: '0 0 0', found: '2 4 0'