QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#428329 | #8770. Comparator | ucup-team1198# | AC ✓ | 636ms | 10692kb | C++20 | 8.0kb | 2024-06-01 18:46:58 | 2024-06-01 18:46:58 |
Judging History
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'