QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#435972#8770. ComparatorieeAC ✓273ms5412kbC++172.2kb2024-06-08 22:42:272024-06-08 22:42:27

Judging History

你现在查看的是最新测评结果

  • [2024-06-08 22:42:27]
  • 评测
  • 测评结果:AC
  • 用时:273ms
  • 内存:5412kb
  • [2024-06-08 22:42:27]
  • 提交

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'