QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#435972 | #8770. Comparator | iee | AC ✓ | 273ms | 5412kb | C++17 | 2.2kb | 2024-06-08 22:42:27 | 2024-06-08 22:42:27 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
inline void cmin(int &x, int y) { if (y < x) x = y; }
map<char, int> p;
void prepare() {
p[')'] = -2;
p['('] = -1;
p['^'] = 0;
p['|'] = 1;
p['&'] = 2;
p['='] = 3;
p['!'] = 4;
}
int calc(int a, int b, int op) {
if (op == 0) return a ^ b;
if (op == 1) return a | b;
if (op == 2) return a & b;
if (op == 3) return a == b;
assert(false);
}
int calc(string expr, char x, char y) {
replace(expr.begin(), expr.end(), 'x', x);
replace(expr.begin(), expr.end(), 'y', y);
vector<int> z, o;
auto Pop = [&]() {
if (o.back() == '!') z.back() ^= 1;
else *prev(z.end(), 2) = calc(z.back(), *prev(z.end(), 2), p[o.back()]), z.pop_back();
o.pop_back();
};
for (int _ = (int) expr.size() - 1; _ >= 0; _--) {
char s = expr[_];
if (isdigit(s)) z.push_back(s - '0');
else if (s == ')') o.push_back(')');
else {
while (o.size() && p[o.back()] >= p[s]) {
Pop();
}
if (s == '(') assert(o.back() == ')'), o.pop_back();
else o.push_back(s);
}
}
while (o.size()) {
Pop();
}
return z.back();
}
int main() {
cin.tie(0)->sync_with_stdio(0);
prepare();
int n, k;
cin >> n >> k;
vector<int> rez(n + 1);
vector f(k, vector(2, vector(k, vector(2, n))));
for (int i = 0; i < n; i++) {
int u, v;
string expr;
cin >> u >> v >> expr >> rez[i], u--, v--;
for (int x : {0, 1}) {
for (int y : {0, 1}) {
if (calc(expr, x + '0', y + '0')) {
cmin(f[u][x][v][y], i);
}
}
}
}
cin >> rez[n];
vector<bitset<1024>> g(1 << k), og(1 << k);
vector e(1 << k, vector<bool>(1 << k));
for (int S = 0; S < (1 << k); S++) {
for (int T = 0; T < (1 << k); T++) {
int pos = n;
for (int i = 0; i < k; i++) {
for (int j = 0; j < k; j++) {
pos = min(pos, f[i][S >> i & 1][j][T >> j & 1]);
}
}
if (rez[pos]) e[S][T] = 1, g[S].set(T);
else og[S].set(T);
}
}
int r1 = 0, r2 = 0, r3 = 0;
for (int x = 0; x < (1 << k); x++) {
r1 += e[x][x];
for (int y = 0; y < (1 << k); y++) {
r2 += e[x][y] && e[y][x];
if (e[x][y]) r3 += (g[y] & og[x]).count();
}
}
cout << r1 << " " << r2 << " " << r3 << "\n";
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3576kb
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: 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: 67ms
memory: 3668kb
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: 273ms
memory: 4496kb
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: 34ms
memory: 5412kb
input:
1 3 1 1 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!...
output:
4 16 0
result:
ok single line: '4 16 0'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3576kb
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: 3576kb
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: 3640kb
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: 3576kb
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: 93ms
memory: 3840kb
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: 3648kb
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: 6ms
memory: 4312kb
input:
1 1 1 1 ((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...
output:
1 1 0
result:
ok single line: '1 1 0'
Test #13:
score: 0
Accepted
time: 218ms
memory: 4696kb
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: 3588kb
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: 3872kb
input:
0 3 1
output:
8 64 0
result:
ok single line: '8 64 0'