QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#437165 | #8770. Comparator | USP_USP_USP | AC ✓ | 375ms | 287684kb | C++20 | 4.2kb | 2024-06-09 06:15:38 | 2024-06-09 06:15:38 |
Judging History
answer
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define int ll
void dbg_out() { cerr << endl; }
template<typename H, typename... T>
void dbg_out(H h, T... t) { cerr << ' ' << h; dbg_out(t...); }
#define dbg(...) { cerr << #__VA_ARGS__ << ':'; dbg_out(__VA_ARGS__); }
bool rec(const string& s, int&i, bool token){
if(token){
if(s[i] == '0'){
i++;
return 0;
}
if(s[i] == '1'){
i++;
return 1;
}
if(s[i] == '!'){
i++;
return 1^rec(s,i,token);
}
if(s[i] == '('){
i++;
int u = rec(s,i,0);
i++;
return u;
}
assert(0);
}else{
int op = 0;
vector<int> values;
//0 = or, 1 = xor, 2 = &, 3 = equal
while(true){
bool at = rec(s,i,1);
values.push_back(at);
int sz = s.size();
if(i == sz) break;
if(s[i] == '|'){
op = 0;
}else if(s[i] == '&'){
op = 2;
}else if(s[i] == '^'){
op = 1;
}else if(s[i] == '='){
op = 3;
}else{
break;
}
values.push_back(op);
i++;
}
vector<int> ordem = {3,2,0,1};
for(auto OP : ordem){
vector<int> nx;
// = & | ^
int sz = values.size();
nx.push_back(values[0]);
for(int h = 1; h < sz; h += 2){
if(values[h] == OP){
int u = nx.back();
nx.pop_back();
int result = 0;
int v = values[h+1];
if(OP == 3){
result = v == u;
}else if(OP == 2){
result = v & u;
}else if(OP == 1){
result = v ^ u;
}else{
result = v | u;
}
nx.push_back(result);
}else{
nx.push_back(values[h]);
nx.push_back(values[h+1]);
}
}
values = nx;
}
return values[0];
}
assert(0);
return false;
}
string transform(string s, int x, int y){
int sz = s.size();
for(int i = 0; i < sz; i++){
if(s[i] == 'x'){
s[i] = char('0'+x);
}
if(s[i] == 'y'){
s[i] = char('0'+y);
}
}
return s;
}
array<int,4> truetable(string s){
array<int,4> retorno;
for(int x = 0; x < 2; x++){
for(int y = 0; y < 2; y++){
string t = transform(s,x,y);
int po = 0;
bool ret = rec(t,po,0);
retorno[x*2 + y] = ret;
}
}
return retorno;
}
int mapeia[11][11][2][2];
int tempo[11][11][2][2];
using bit = bitset<1100>;
void solve() {
int n,k;
cin >> n >> k;
for(int i = 0; i < k; i++){
for(int j = 0; j < k; j++){
for(int w = 0; w < 2; w++){
for(int z = 0; z < 2; z++){
mapeia[i][j][w][z] = -1;
}
}
}
}
for(int i = 0; i < n; i++){
int A,B;
cin >> A >> B;
A--;
B--;
string s;
cin >> s;
array<int,4> at = truetable(s);
//for(int i = 0; i < 4; i++){
// cout << at[i] << ' ';
//}
int retval;
cin >> retval;
for(int x = 0; x < 2; x++){
for(int y = 0; y < 2; y++){
if(mapeia[A][B][x][y] != -1) continue;
int id = x*2+y;
if(at[id]){
mapeia[A][B][x][y] = retval;
tempo[A][B][x][y] = i;
}
}
}
}
int base;
cin >> base;
for(int i = 0; i < k; i++){
for(int j = 0; j < k; j++){
for(int w = 0; w < 2; w++){
for(int z = 0; z < 2; z++){
if(mapeia[i][j][w][z] == -1){
mapeia[i][j][w][z] = base;
tempo[i][j][w][z] = n;
}
}
}
}
}
vector<bit> g((1<<k));
for(int mask1 = 0; mask1 < (1<<k); mask1++){
for(int mask2 = 0; mask2 < (1<<k); mask2++){
int val = base;
int tem = n;
for(int i = 0; i < k; i++){
for(int j = 0; j < k; j++){
int x = (mask1>>i)&1;
int y = (mask2>>j)&1;
if(tempo[i][j][x][y] < tem){
tem = tempo[i][j][x][y];
val = mapeia[i][j][x][y];
}
}
}
g[mask1][mask2] = val;
}
}
int refle = 0;
for(int mask = 0; mask < (1<<k); mask++){
refle += g[mask][mask];
}
int sime = 0;
for(int mask1 = 0; mask1 < (1<<k); mask1++){
for(int mask2 = 0; mask2 < (1<<k); mask2++){
if(g[mask1][mask2] == 1){
sime += g[mask2][mask1];
}
}
}
int trans = 0;
for(int mask1 = 0; mask1 < (1<<k); mask1++){
bit neg = g[mask1];
for(int mask2 = 0; mask2 < (1<<k); mask2++){
if(neg[mask2]) neg[mask2] = 0;
else neg[mask2] = 1;
}
for(int mask2 = 0; mask2 < (1<<k); mask2++){
if(g[mask1][mask2]){
bit at = neg&g[mask2];
trans += at.count();
}
}
}
cout << refle << ' ' << sime << ' ' << trans <<'\n';
}
signed main() {
ios::sync_with_stdio(false); cin.tie(0);
solve();
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3612kb
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: 3800kb
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: 168ms
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:
4 16 0
result:
ok single line: '4 16 0'
Test #4:
score: 0
Accepted
time: 375ms
memory: 3632kb
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: 202ms
memory: 287684kb
input:
1 3 1 1 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!...
output:
4 16 0
result:
ok single line: '4 16 0'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3728kb
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: 3776kb
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: 3544kb
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: 1ms
memory: 3552kb
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: 91ms
memory: 3728kb
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: 3620kb
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: 65ms
memory: 60284kb
input:
1 1 1 1 ((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...
output:
1 1 0
result:
ok single line: '1 1 0'
Test #13:
score: 0
Accepted
time: 337ms
memory: 3560kb
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: 3624kb
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: 3780kb
input:
0 3 1
output:
8 64 0
result:
ok single line: '8 64 0'