QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #528646 | #8770. Comparator | LittleCube | WA | 111ms | 3764kb | C++17 | 4.2kb | 2024-08-23 18:25:15 | 2024-08-23 18:25:15 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<double, double>
#define F first
#define S second
#define all(x) x.begin(), x.end()
using namespace std;
int pri(char c)
{
switch(c)
{
case '=':
return 1;
case '&':
return 2;
case '|':
return 3;
case '^':
return 4;
case ')':
return 5;
case '(':
return 6;
}
return 0;
}
int eval(string s, int x, int y)
{
vector<int> res;
vector<char> ops;
s = "(" + s + ")";
for (auto c : s)
{
if ("xy01"s.find(c) != string::npos)
{
if (c == 'x')
res.emplace_back(x);
else if (c == 'y')
res.emplace_back(y);
else if (c == '0')
res.emplace_back(0);
else if (c == '1')
res.emplace_back(1);
while (ops.back() == '!')
res.back() = !res.back(), ops.pop_back();
}
else if (c == '(')
ops.emplace_back('(');
else if ("=&|^)"s.find(c) != string::npos)
{
while (pri(ops.back()) <= pri(c))
{
int b = res.back(); res.pop_back();
int a = res.back(); res.pop_back();
if (ops.back() == '=')
res.emplace_back(a == b);
else if (ops.back() == '&')
res.emplace_back(a && b);
else if (ops.back() == '^')
res.emplace_back(a ^ b);
else if (ops.back() == '|')
res.emplace_back(a || b);
ops.pop_back();
}
if (c == ')')
{
ops.pop_back(); // (
while (!ops.empty() && ops.back() == '!')
res.back() = !res.back(), ops.pop_back();
}
else ops.emplace_back(c);
}
else if (c == '!')
ops.emplace_back('!');
}
return res.back();
}
int N, K;
pii rule[10][10][2][2], res[1024][10][2];
bitset<1024> G[1024];
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> N >> K;
for (int i = 0; i < K; i++)
for (int j = 0; j < K; j++)
for (int x = 0; x <= 1; x++)
for (int y = 0; y <= 1; y++)
rule[i][j][x][y] = pii(N + 2, -1);
for (int i = 1; i <= N; i++)
{
int a, b, ret;
string s;
cin >> a >> b >> s >> ret;
a--, b--;
for (int x = 0; x <= 1; x++)
for (int y = 0; y <= 1; y++)
if (eval(s, x, y))
rule[a][b][x][y] = pii(i, ret);
}
int def;
cin >> def;
for (int i = 0; i < K; i++)
for (int j = 0; j < K; j++)
for (int x = 0; x <= 1; x++)
for (int y = 0; y <= 1; y++)
rule[i][j][x][y] = min(rule[i][j][x][y], pii(N + 1, def));
for (int i = 0; i < (1 << K); i++)
for (int j = 0; j < K; j++)
for (int y = 0; y <= 1; y++)
{
res[i][j][y] = pii(N + 1, def);
for (int k = 0; k < K; k++)
res[i][j][y] = min(res[i][j][y], rule[k][j][(i >> k) & 1][y]);
}
for (int i = 0; i < (1 << K); i++)
for (int j = 0; j < (1 << K); j++)
{
pii ret = pii(N + 1, def);
for (int k = 0; k < K; k++)
ret = min(ret, res[i][k][(j >> k) & 1]);
G[i][j] = (ret.S != 0);
}
int bad = 0;
for (int i = 0; i < (1 << K); i++)
if (G[i][i]) bad++;
cout << bad << ' ';
bad = 0;
for (int i = 0; i < (1 << K); i++)
for (int j = 0; j < (1 << K); j++)
if (G[i][j] && G[j][i]) bad++;
cout << bad << ' ';
bad = 0;
for (int i = 0; i < (1 << K); i++)
for (int j = 0; j < (1 << K); j++)
if (G[i][j])
bad += (G[j] & (~G[i])).count();
cout << bad << '\n';
}
/*
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
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3580kb
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: 3580kb
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: -100
Wrong Answer
time: 111ms
memory: 3764kb
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:
5 41 48
result:
wrong answer 1st lines differ - expected: '4 16 0', found: '5 41 48'