QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#429604 | #8770. Comparator | rniya | AC ✓ | 250ms | 82372kb | C++23 | 6.9kb | 2024-06-02 17:57:44 | 2024-06-02 17:57:46 |
Judging History
answer
#include <bits/stdc++.h>
#ifdef LOCAL
#include <debug.hpp>
#else
#define debug(...) void(0)
#endif
template <class T> std::istream& operator>>(std::istream& is, std::vector<T>& v) {
for (auto& e : v) {
is >> e;
}
return is;
}
template <class T> std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
for (std::string_view sep = ""; const auto& e : v) {
os << std::exchange(sep, " ") << e;
}
return os;
}
template <class T, class U = T> bool chmin(T& x, U&& y) {
return y < x and (x = std::forward<U>(y), true);
}
template <class T, class U = T> bool chmax(T& x, U&& y) {
return x < y and (x = std::forward<U>(y), true);
}
template <class T> void mkuni(std::vector<T>& v) {
std::ranges::sort(v);
auto result = std::ranges::unique(v);
v.erase(result.begin(), result.end());
}
template <class T> int lwb(const std::vector<T>& v, const T& x) {
return std::distance(v.begin(), std::ranges::lower_bound(v, x));
}
using ll = long long;
using namespace std;
vector<vector<int>> value(const string&, int&);
vector<vector<int>> term(const string&, int&);
vector<vector<int>> expression(const string&, int&);
vector<vector<int>> value(const string& s, int& cur) {
vector res(2, vector<int>(2));
char c = s[cur++];
if (islower(c)) {
assert(c == 'x' or c == 'y');
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
res[i][j] = (c == 'x' ? i : j);
}
}
} else if (isdigit(c)) {
assert(c == '0' or c == '1');
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
res[i][j] = c - '0';
}
}
} else {
assert(false);
}
return res;
}
vector<vector<int>> term(const string& s, int& cur) {
if (s[cur] == '(') {
auto res = expression(s, ++cur);
assert(s[cur++] == ')');
return res;
} else if (s[cur] == '!') {
auto res = term(s, ++cur);
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
res[i][j] ^= 1;
}
}
return res;
} else {
return value(s, cur);
}
}
// vector<vector<int>> expression(const string& s, int& cur) {
// auto res = term(s, cur);
// while (cur < int(s.size())) {
// char op = s[cur];
// if (not(op == '=' or op == '&' or op == '|' or op == '^')) {
// assert(op == ')');
// break;
// }
// cur++;
// auto R = term(s, cur);
// for (int i = 0; i < 2; i++) {
// for (int j = 0; j < 2; j++) {
// auto& x = res[i][j];
// auto y = R[i][j];
// if (op == '=') {
// x = x == y;
// } else if (op == '&') {
// x = x & y;
// } else if (op == '|') {
// x = x | y;
// } else {
// assert(op == '^');
// x = x ^ y;
// }
// }
// }
// }
// return res;
// }
vector<vector<int>> parseEquals(const string& s, int& cur) {
auto res = term(s, cur);
while (cur < int(s.size()) && s[cur] == '=') {
cur++;
auto R = term(s, cur);
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
res[i][j] = (res[i][j] == R[i][j]);
}
}
}
return res;
}
vector<vector<int>> parseAnd(const string& s, int& cur) {
auto res = parseEquals(s, cur);
while (cur < int(s.size()) && s[cur] == '&') {
cur++;
auto R = parseEquals(s, cur);
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
res[i][j] &= R[i][j];
}
}
}
return res;
}
vector<vector<int>> parseOr(const string& s, int& cur) {
auto res = parseAnd(s, cur);
while (cur < int(s.size()) && s[cur] == '|') {
cur++;
auto R = parseAnd(s, cur);
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
res[i][j] |= R[i][j];
}
}
}
return res;
}
vector<vector<int>> parseXor(const string& s, int& cur) {
auto res = parseOr(s, cur);
while (cur < int(s.size()) && s[cur] == '^') {
cur++;
auto R = parseOr(s, cur);
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
res[i][j] ^= R[i][j];
}
}
}
return res;
}
vector<vector<int>> expression(const string& s, int& cur) { return parseXor(s, cur); }
const int MAX_K = 10;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(15);
int n, K;
cin >> n >> K;
vector<int> a(n), b(n), r(n);
vector<string> expr(n);
for (int i = 0; i < n; i++) {
cin >> a[i] >> b[i] >> expr[i] >> r[i];
a[i]--, b[i]--;
}
int last;
cin >> last;
vector e(n, vector(2, vector<int>(2)));
for (int i = 0; i < n; i++) {
int init = 0;
e[i] = expression(expr[i], init);
}
{
vector<int> na, nb, nr;
vector<vector<vector<int>>> ne;
set<tuple<int, int, vector<vector<int>>>> s;
for (int i = 0; i < n; i++) {
auto tmp = make_tuple(a[i], b[i], e[i]);
if (s.count(tmp)) continue;
na.emplace_back(a[i]);
nb.emplace_back(b[i]);
ne.emplace_back(e[i]);
nr.emplace_back(r[i]);
s.emplace(tmp);
}
swap(a, na);
swap(b, nb);
swap(e, ne);
swap(r, nr);
n = a.size();
}
vector f(1 << K, vector<int>(1 << K, -1));
for (int i = 0; i < 1 << K; i++) {
set<pair<int, int>> s;
for (int k = 0; k < n; k++) {
int x = i >> a[k] & 1;
for (int d = 0; d < 2; d++) {
if (not e[k][x][d]) continue;
if (s.count({b[k], d})) continue;
for (int j = 0; j < 1 << K; j++) {
if (f[i][j] == -1 and (j >> b[k] & 1) == d) {
f[i][j] = r[k];
}
}
s.emplace(b[k], d);
}
}
for (int j = 0; j < 1 << K; j++) {
if (f[i][j] == -1) {
f[i][j] = last;
}
}
}
vector<ll> ans(3, 0);
vector<bitset<1 << MAX_K>> F(1 << K);
for (int i = 0; i < 1 << K; i++) {
for (int j = 0; j < 1 << MAX_K; j++) {
F[i][j] = 0;
}
for (int j = 0; j < 1 << K; j++) {
F[i][j] = f[i][j];
}
}
for (int x = 0; x < 1 << K; x++) {
ans[0] += not(f[x][x] == 0);
for (int y = 0; y < 1 << K; y++) {
if (f[x][y]) {
ans[1] += not(f[y][x] == 0);
ans[2] += F[y].count() - (F[x] & F[y]).count();
}
}
}
cout << ans << '\n';
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3484kb
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: 3792kb
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: 33ms
memory: 4908kb
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: 250ms
memory: 38580kb
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: 19ms
memory: 82372kb
input:
1 3 1 1 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!...
output:
4 16 0
result:
ok single line: '4 16 0'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3596kb
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: 3796kb
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: 0ms
memory: 3732kb
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: 3524kb
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: 3ms
memory: 7720kb
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: 3796kb
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: 3ms
memory: 55200kb
input:
1 1 1 1 ((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...
output:
1 1 0
result:
ok single line: '1 1 0'
Test #13:
score: 0
Accepted
time: 127ms
memory: 41524kb
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: 3480kb
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: 3520kb
input:
0 3 1
output:
8 64 0
result:
ok single line: '8 64 0'