QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#446024 | #8770. Comparator | w4p3r | AC ✓ | 278ms | 19352kb | C++20 | 4.8kb | 2024-06-16 19:49:55 | 2024-06-16 19:49:55 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define N 200010
#define K 10
int n, k;
bool B[N][2][2];
int a[N], b[N], w[N];
int ans[K][K][2][2];
bool sol(string a, int p, int q)
{
stack<int>S;
/*
-1 -> '!'
-2 -> '='
-3 -> '&'
-4 -> '|'
-5 -> '^'
-6 -> '('
*/
int len = a.length();
vector<int>ans;
// cout << "??:" << a << endl;
for (int i = 0; i < len; i ++)
{
if (a[i] == 'x') {ans.push_back(p); continue;}
if (a[i] == 'y') {ans.push_back(q); continue;}
if (a[i] == '0') {ans.push_back(0); continue;}
if (a[i] == '1') {ans.push_back(1); continue;}
if (a[i] == '(') {S.push(-6); continue;}
if (a[i] == ')')
{
if (S.empty())while(true);
while (S.top() != -6)
{
int x = S.top();
ans.push_back(x);
S.pop(); if (S.empty())while(true);
}
S.pop();
continue;
}
int op = 0;
if (a[i] == '!') op = -1;
if (a[i] == '=') op = -2;
if (a[i] == '&') op = -3;
if (a[i] == '|') op = -4;
if (a[i] == '^') op = -5;
if (S.empty())while(true);
while(S.top() > op)
{
int x = S.top();
ans.push_back(x);
S.pop();
if (S.empty())while(true);
}
S.push(op);
}
// cout << S.top() << endl;
// assert(S.empty());
if (!S.empty()) while(true);
int n = ans.size();
// cout << "GG:" << p << ' ' << q << endl;
// for (int i = 0; i < n; i ++) cout << ans[i] << ' '; cout << endl;
// cout << "??:" << S.size() << endl;
// while (!S.empty()) {cout << S.top() << ' '; S.pop();} cout << endl;
for (int i = 0; i < n; i ++)
{
if (ans[i] >= 0) S.push(ans[i]);
else
{
if (ans[i] == -1)
{
// if (S.empty())while(true);
int x = S.top(); S.pop();
S.push(!x);
}
else
{
// if (S.empty())while(true);
int x = S.top(); S.pop();
// if (S.empty())while(true);
int y = S.top(); S.pop();
int w;
if (ans[i] == -2) w = (x == y);
if (ans[i] == -3) w = (x & y);
if (ans[i] == -4) w = (x | y);
if (ans[i] == -5) w = (x ^ y);
// cout << "EEE:" << i << " " << w << endl;
S.push(w);
}
}
}
// if(S.empty())while(true);
int Ans = S.top(); S.pop();
// if(!S.empty()) while(true);
// cout << "???:" << Ans << endl;
// assert(S.empty());
return Ans;
}
bool f[1 << K][1 << K];
int Ans1, Ans2;
long long Ans3;
bitset<1 << K>P[1 << K], Q[1 << K];
int main() {
ios::sync_with_stdio(0); cin.tie(nullptr);
cin >> n >> k;
for (int i = 1; i <= n; i ++)
{
cin >> a[i] >> b[i];
a[i] --, b[i] --;
string s;
cin >> s >> w[i];
s = "(" + s + ")";
for (int p = 0; p < 2; p ++)
{
for (int q = 0; q < 2; q ++)
{
B[i][p][q] = sol(s, p, q);
}
}
}
cin >> w[n + 1];
for (int i = 0; i < k; i ++) for (int j = 0; j < k; j ++) for (int p = 0; p < 2; p ++) for (int q = 0; q < 2; q ++) ans[i][j][p][q] = n + 1;
for (int x = 1; x <= n; x ++)
{
for (int p = 0; p < 2; p ++) for (int q = 0; q < 2; q ++) if(B[x][p][q])
{
ans[a[x]][b[x]][p][q] = min(ans[a[x]][b[x]][p][q], x);
}
}
for (int i = 0; i < (1 << k); i ++) for (int j = 0; j < (1 << k); j ++)
{
int id = n + 1;
for (int x = 0; x < k; x ++) for (int y = 0; y < k; y ++)
{
int p = (i >> x) & 1, q = (j >> y) & 1;
id = min(id, ans[x][y][p][q]);
}
f[i][j] = w[id];
}
for (int i = 0; i < (1 << k); i ++)Ans1 += f[i][i];
for (int i = 0; i < (1 << k); i ++)
{
for (int j = 0; j < (1 << k); j ++) if(f[i][j])
{
Ans2 += (f[j][i]);
}
}
for (int i = 0; i < (1 << k); i ++)
{
for (int j = 0; j < (1 << k); j ++) if (f[i][j])
{
P[i][j] = 1, Q[j][i] = 1;
}
}
for (int i = 0; i < (1 << k); i ++)
{
for (int j = 0; j < (1 << k); j ++) if (!f[i][j])
{
Ans3 += (P[i] & Q[j]).count();
}
}
cout << Ans1 << ' ' << Ans2 << ' ' << Ans3 << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7652kb
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: 5620kb
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: 43ms
memory: 5768kb
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: 262ms
memory: 7952kb
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: 27ms
memory: 19352kb
input:
1 3 1 1 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!...
output:
4 16 0
result:
ok single line: '4 16 0'
Test #6:
score: 0
Accepted
time: 1ms
memory: 5564kb
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: 1ms
memory: 5896kb
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: 5676kb
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: 5612kb
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: 163ms
memory: 6944kb
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: 5904kb
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: 0ms
memory: 6228kb
input:
1 1 1 1 ((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...
output:
1 1 0
result:
ok single line: '1 1 0'
Test #13:
score: 0
Accepted
time: 278ms
memory: 8244kb
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: 5916kb
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: 1ms
memory: 5632kb
input:
0 3 1
output:
8 64 0
result:
ok single line: '8 64 0'