QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #428588 | #8770. Comparator | ucup-team228# | AC ✓ | 584ms | 48176kb | C++20 | 9.8kb | 2024-06-01 20:33:01 | 2024-06-01 20:33:02 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Func {
int res[2][2] = {};
Func(char ch = '0') {
if (ch == 'x') {
for (int x = 0; x <= 1; x++) {
for (int y = 0; y <= 1; y++) {
res[x][y] = x;
}
}
} else if (ch == 'y') {
for (int x = 0; x <= 1; x++) {
for (int y = 0; y <= 1; y++) {
res[x][y] = y;
}
}
} else if (ch == '0') {
for (int x = 0; x <= 1; x++) {
for (int y = 0; y <= 1; y++) {
res[x][y] = 0;
}
}
} else {
for (int x = 0; x <= 1; x++) {
for (int y = 0; y <= 1; y++) {
res[x][y] = 1;
}
}
}
}
int operator()(int x, int y) const {
return res[x][y];
}
};
ostream& operator<<(ostream& ostr, const Func& func) {
for (int i = 0; i <= 1; i++) {
for (int j = 0; j <= 1; j++) {
ostr << func.res[i][j];
}
ostr << "\n";
}
return ostr;
}
struct LongFunc {
int a = 0, b = 0;
string expr;
int r = -1;
};
istream& operator>>(istream& istr, LongFunc& long_func) {
return istr >> long_func.a >> long_func.b >> long_func.expr >> long_func.r;
}
bool is_operator(char ch) {
return ch == '!' || ch == '=' || ch == '&' || ch == '|' || ch == '^';
}
const int L = 1e6 + 10;
vector<int> g[L];
Func eval(int l, int r, const LongFunc& long_func) {
assert(l == r); // must be one of the 'x', 'y', '0', or '1'
return long_func.expr[l];
}
Func change_not(Func func) {
for (int i = 0; i <= 1; i++) {
for (int j = 0; j <= 1; j++) {
func.res[i][j] ^= 1;
}
}
return func;
}
Func merge_eq(const Func& lhs, const Func& rhs) {
Func res;
for (int i = 0; i <= 1; i++) {
for (int j = 0; j <= 1; j++) {
res.res[i][j] = lhs.res[i][j] == rhs.res[i][j];
}
}
return res;
}
Func merge_and(const Func& lhs, const Func& rhs) {
Func res;
for (int i = 0; i <= 1; i++) {
for (int j = 0; j <= 1; j++) {
res.res[i][j] = lhs.res[i][j] & rhs.res[i][j];
}
}
return res;
}
Func merge_or(const Func& lhs, const Func& rhs) {
Func res;
for (int i = 0; i <= 1; i++) {
for (int j = 0; j <= 1; j++) {
res.res[i][j] = lhs.res[i][j] | rhs.res[i][j];
}
}
return res;
}
Func merge_xor(const Func& lhs, const Func& rhs) {
Func res;
for (int i = 0; i <= 1; i++) {
for (int j = 0; j <= 1; j++) {
res.res[i][j] = lhs.res[i][j] ^ rhs.res[i][j];
}
}
return res;
}
Func merge(const Func& lhs, const Func& rhs, char trg_op) {
if (trg_op == '=') {
return merge_eq(lhs, rhs);
} else if (trg_op == '&') {
return merge_and(lhs, rhs);
} else if (trg_op == '|') {
return merge_or(lhs, rhs);
} else if (trg_op == '^') {
return merge_xor(lhs, rhs);
} else {
assert(false);
}
}
Func dfs(int v, const LongFunc& long_func) {
assert(long_func.expr[g[v].back()] == ')');
vector<pair<char, Func>> cur;
for (int i = 0; i + 1 < g[v].size(); i++) {
int l = g[v][i], r = g[v][i + 1] - 1;
if (long_func.expr[l] == '(') {
cur.emplace_back('f', dfs(l, long_func));
} else if (!is_operator(long_func.expr[l])) {
cur.emplace_back('f', eval(l, r, long_func));
} else {
assert(l == r);
cur.emplace_back(long_func.expr[l], Func());
}
}
vector<pair<char, Func>> nxt;
{ // !
nxt.clear();
bool flag = false;
for (const auto& [op, func] : cur) {
if (op == '!') {
flag ^= 1;
} else {
if (flag) {
assert(op == 'f');
nxt.emplace_back(op, change_not(func));
flag = false;
} else {
nxt.emplace_back(op, func);
}
}
}
swap(cur, nxt);
}
for (char trg_op : "=&|^") {
nxt.clear();
bool flag = false;
for (const auto& [op, func] : cur) {
if (op == trg_op) {
flag = true;
} else {
if (flag) {
assert(op == 'f' && !nxt.empty() && nxt.back().first == 'f');
auto prev = nxt.back().second;
nxt.pop_back();
nxt.emplace_back(op, merge(prev, func, trg_op));
flag = false;
} else {
nxt.emplace_back(op, func);
}
}
}
swap(cur, nxt);
}
// cout << cur.size() << endl;
assert(cur.size() == 1 && cur.front().first == 'f');
return cur.front().second;
}
Func parse(LongFunc long_func) {
int n = long_func.expr.size();
long_func.expr = "(" + long_func.expr + ")";
for (int i = 0; i <= n + 1; i++) {
g[i].clear();
}
stack<int> st;
st.push(0);
for (int i = 1; i <= n + 1; i++) {
g[st.top()].push_back(i);
if (long_func.expr[i] == '(') {
st.push(i);
} else if (long_func.expr[i] == ')') {
st.pop();
}
}
return dfs(0, long_func);
}
const int N = 2e5 + 10;
const int K = 10;
const int M = (1 << K) + 10;
LongFunc long_func[N];
Func func[N];
int f[M][M];
bitset<M> bs[M];
int getbit(int mask, int bit) {
return (mask >> bit) & 1;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> long_func[i];
}
int final_res;
cin >> final_res;
// n = 2e5;
// k = 10;
// for (int i = 1; i <= n; i++) {
// long_func[i].a = 0;
// long_func[i].b = 0;
// long_func[i].expr = "y";
// long_func[i].r = 0;
// }
for (int i = 1; i <= n; i++) {
func[i] = parse(long_func[i]);
// cout << long_func[i].expr << "\n";
// cout << func[i] << "\n";
}
auto generate = [&](const vector<int>& bits) {
vector<int> pos;
for (int i = 0; i < k; i++) {
if (bits[i] == -1) {
pos.push_back(i);
}
}
vector<int> res;
for (int mask = 0; mask < (1 << pos.size()); mask++) {
int cur = 0;
for (int i = 0; i < k; i++) {
if (bits[i] == 1) {
cur |= (1 << i);
}
}
for (int i = 0; i < pos.size(); i++) {
if (getbit(mask, i)) {
cur |= (1 << pos[i]);
}
}
res.push_back(cur);
}
return res;
};
for (int x = 0; x < (1 << k); x++) {
vector<int> bits(k, -1);
bool was_stopped = false;
for (int i = 1; i <= n; i++) {
int a = long_func[i].a - 1;
int b = long_func[i].b - 1;
int r = long_func[i].r;
int res[2] = {
func[i](getbit(x, a), 0),
func[i](getbit(x, a), 1)
};
if (res[0] != res[1]) {
bool is_id = res[0] == 0;
int cur_bit = is_id ? 1 : 0;
if (bits[b] == -1) {
bits[b] = cur_bit;
vector<int> ys = generate(bits);
for (int y : ys) {
f[x][y] = r;
}
bits[b] = cur_bit ^ 1;
} else {
if (bits[b] == cur_bit) {
vector<int> ys = generate(bits);
for (int y : ys) {
f[x][y] = r;
}
was_stopped = true;
break;
} else {
// skip
}
}
} else {
if (res[0] == 0) {
// expression always 0 and skips through
} else {
// expression always 1 and need to stop
vector<int> ys = generate(bits);
for (int y : ys) {
f[x][y] = r;
}
was_stopped = true;
break;
}
}
}
if (!was_stopped) {
vector<int> ys = generate(bits);
for (int y : ys) {
f[x][y] = final_res;
}
}
}
for (int x = 0; x < (1 << k); x++) {
for (int y = 0; y < (1 << k); y++) {
bs[x][y] = f[x][y];
}
}
ll ans1 = 0, ans2 = 0, ans3 = 0;
for (int x = 0; x < (1 << k); x++) {
ans1 += f[x][x] != 0;
}
for (int x = 0; x < (1 << k); x++) {
for (int y = 0; y < (1 << k); y++) {
ans2 += f[x][y] && f[y][x];
}
}
for (int x = 0; x < (1 << k); x++) {
for (int y = 0; y < (1 << k); y++) {
if (f[x][y]) {
ans3 += bs[y].count() - (bs[y] & bs[x]).count();
}
}
}
cout << ans1 << " " << ans2 << " " << ans3 << "\n";
#ifdef LOCAL
cout << "\nTime elapsed: " << double(clock()) / CLOCKS_PER_SEC << " s.\n";
#endif
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 18180kb
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: 17904kb
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: 47ms
memory: 19260kb
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: 228ms
memory: 22208kb
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: 8ms
memory: 48176kb
input:
1 3 1 1 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!...
output:
4 16 0
result:
ok single line: '4 16 0'
Test #6:
score: 0
Accepted
time: 4ms
memory: 17952kb
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: 5ms
memory: 18096kb
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: 17956kb
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: 4ms
memory: 17896kb
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: 49ms
memory: 22832kb
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: 17872kb
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: 8ms
memory: 44988kb
input:
1 1 1 1 ((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...
output:
1 1 0
result:
ok single line: '1 1 0'
Test #13:
score: 0
Accepted
time: 584ms
memory: 21300kb
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: 5ms
memory: 18204kb
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: 4ms
memory: 17840kb
input:
0 3 1
output:
8 64 0
result:
ok single line: '8 64 0'