QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#89574 | #5250. Combination Locks | sky3142 | AC ✓ | 7ms | 3392kb | C++20 | 1.7kb | 2023-03-20 16:43:14 | 2023-03-20 16:43:18 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
constexpr int N = 10;
int n;
int matched[1 << N];
bool canuse[1 << N];
bool vis[1 << N];
bool left(unsigned u)
{
return popcount(u) % 2 == 0;
}
bool dfs(int u)
{
if (vis[u])
return false;
vis[u] = true;
for (int i = 0; i < n; ++i)
{
int v = u ^ (1 << i);
if (canuse[v] && (matched[v] == -1 || dfs(matched[v])))
{
matched[v] = u;
return true;
}
}
return false;
}
int max_match()
{
int res = 0;
fill_n(matched, 1 << n, -1);
for (int i = 0; i < (1 << n); ++i)
{
if (left(i) && canuse[i])
{
fill_n(vis, 1 << n, false);
if (dfs(i))
++res;
}
}
return res;
}
void solve()
{
int m;
cin >> n >> m;
int start = 0;
string s1, s2;
cin >> s1;
cin >> s2;
for (int i = 0; i < n; ++i)
{
if (s1[i] == s2[i])
start |= 1 << i;
}
fill_n(canuse, 1 << n, true);
for (int i = 0; i < m; ++i)
{
string s;
cin >> s;
int cur = 0;
for (int i = 0; i < n; ++i)
{
if (s[i] == '=')
cur |= 1 << i;
}
canuse[cur ^ start] = false;
}
int match1 = max_match();
canuse[0] = false;
int match2 = max_match();
if (match1 == match2)
{
cout << "Bob\n";
}
else
{
cout << "Alice\n";
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--)
{
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3332kb
input:
2 1 0 0 0 1 1 0 0 .
output:
Alice Bob
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 1ms
memory: 3264kb
input:
8 2 0 00 00 2 1 00 00 .. 2 1 00 00 =. 2 2 00 00 .. =. 2 1 00 00 .= 2 2 00 00 .. .= 2 2 00 00 =. .= 2 3 00 00 .. =. .=
output:
Alice Alice Bob Alice Bob Alice Bob Bob
result:
ok 8 lines
Test #3:
score: 0
Accepted
time: 1ms
memory: 3380kb
input:
20 4 4 4714 5245 ..=. ..== .==. ==.. 4 1 2697 1438 .=.. 4 5 9255 0677 ...= ..== =..= ==.= ==== 4 12 3292 7326 ...= ..=. ..== .=.. .=.= .==. =... =..= =.== ==.. ==.= ==== 4 9 8455 2536 ...= ..== .=.. .=.= .==. .=== =... ==.. ===. 4 12 5755 1517 ...= ..=. ..== .=.. .=.= .=== =..= =.=. =.== ==.. ==.= =...
output:
Alice Bob Alice Bob Bob Alice Bob Bob Alice Alice Bob Alice Alice Bob Bob Bob Bob Bob Bob Bob
result:
ok 20 lines
Test #4:
score: 0
Accepted
time: 1ms
memory: 3272kb
input:
20 5 30 99942 90170 ..... ....= ...== ..=.. ..=.= ..==. ..=== .=... .=..= .=.=. .=.== .==.. .==.= .===. .==== =...= =..=. =..== =.=.. =.=.= =.==. =.=== ==... ==..= ==.=. ==.== ===.. ===.= ====. ===== 5 14 11760 95480 ...=. ...== ..=.. ..=.= .=... .=..= .==== =.... =...= =.=.. =.==. ==... ==.== =====...
output:
Bob Alice Alice Alice Alice Bob Bob Bob Alice Alice Alice Bob Alice Alice Alice Alice Alice Alice Alice Bob
result:
ok 20 lines
Test #5:
score: 0
Accepted
time: 1ms
memory: 3272kb
input:
20 6 62 188256 588825 ...... .....= ....=. ....== ...=.. ...=.= ...==. ...=== ..=... ..=..= ..=.=. ..=.== ..==.. ..==.= ..===. ..==== .=.... .=...= .=..=. .=..== .=.=.. .=.=.= .=.==. .=.=== .==..= .==.=. .==.== .===.. .===.= .===== =..... =....= =...=. =...== =..=.. =..=.= =..==. =..=== =.=... =.=.....
output:
Bob Bob Alice Alice Alice Bob Bob Bob Bob Alice Bob Bob Alice Alice Alice Bob Alice Alice Alice Alice
result:
ok 20 lines
Test #6:
score: 0
Accepted
time: 3ms
memory: 3316kb
input:
20 7 34 1829551 8802318 ....=.= ...=.== ...===. ..=..=. ..=..== ..=.==. .=...== .=..=== .=.=.=. .=.==.. .==.... .==...= .==.=.= .==.=== .===.== =.....= =..=.=. =..=.== =..==.. =..==.= =.=.=.. =.=.=.= =.==..= =.==.=. =.===.. =.===.= =.===== ==..... ==..=== ==.==.= ===.... ===..== ====.== =====.= 7 56...
output:
Alice Bob Bob Alice Bob Bob Alice Bob Alice Bob Alice Alice Alice Bob Bob Alice Bob Bob Alice Bob
result:
ok 20 lines
Test #7:
score: 0
Accepted
time: 5ms
memory: 3336kb
input:
20 8 101 98515990 35971617 ......== ....==.. ....==.= ...=.=.. ...=.=.= ...=.==. ...==... ...==.== ...===.. ...===.= ...====. ..=..=.. ..=..==. ..=.=..= ..=.=.== ..=.==.= ..=.===. ..==...= ..==..== ..==.=.. ..==.=.= ..===..= .=...=.. .=...=.= .=...=== .=..=... .=..=..= .=..==.= .=..===. .=..==== .=....
output:
Alice Alice Bob Alice Alice Alice Alice Bob Bob Bob Bob Bob Bob Alice Bob Alice Bob Bob Alice Bob
result:
ok 20 lines
Test #8:
score: 0
Accepted
time: 5ms
memory: 3272kb
input:
20 9 280 799210637 072013670 ......... ......=.= ......==. .....=... .....=..= .....=.=. .....===. .....==== ....=.... ....=.==. ....==... ....==..= ....==.== ....===== ...=..... ...=....= ...=...== ...=..=.. ...=..=.= ...=..==. ...=.=... ...=.=..= ...=.=.=. ...=.=.== ...=.==.= ...=.==== ...==..=. ....
output:
Alice Bob Bob Alice Bob Bob Alice Alice Bob Bob Bob Bob Alice Bob Bob Alice Alice Bob Alice Bob
result:
ok 20 lines
Test #9:
score: 0
Accepted
time: 2ms
memory: 3276kb
input:
20 3 0 000 000 3 1 000 000 ... 3 1 000 000 =.. 3 2 000 000 ... =.. 3 1 000 000 .=. 3 2 000 000 ... .=. 3 2 000 000 =.. .=. 3 3 000 000 ... =.. .=. 3 1 000 000 ==. 3 2 000 000 ... ==. 3 2 000 000 =.. ==. 3 3 000 000 ... =.. ==. 3 2 000 000 .=. ==. 3 3 000 000 ... .=. ==. 3 3 000 000 =.. .=. ==. 3 4 0...
output:
Alice Bob Alice Alice Alice Alice Alice Alice Bob Bob Alice Bob Alice Bob Alice Alice Alice Alice Alice Alice
result:
ok 20 lines
Test #10:
score: 0
Accepted
time: 0ms
memory: 3268kb
input:
20 3 2 000 000 .=. ..= 3 3 000 000 ... .=. ..= 3 3 000 000 =.. .=. ..= 3 4 000 000 ... =.. .=. ..= 3 2 000 000 ==. ..= 3 3 000 000 ... ==. ..= 3 3 000 000 =.. ==. ..= 3 4 000 000 ... =.. ==. ..= 3 3 000 000 .=. ==. ..= 3 4 000 000 ... .=. ==. ..= 3 4 000 000 =.. .=. ==. ..= 3 5 000 000 ... =.. .=. =...
output:
Alice Alice Alice Alice Alice Bob Alice Alice Alice Alice Alice Alice Bob Bob Alice Bob Alice Bob Alice Alice
result:
ok 20 lines
Test #11:
score: 0
Accepted
time: 2ms
memory: 3256kb
input:
20 3 2 000 000 ==. =.= 3 3 000 000 ... ==. =.= 3 3 000 000 =.. ==. =.= 3 4 000 000 ... =.. ==. =.= 3 3 000 000 .=. ==. =.= 3 4 000 000 ... .=. ==. =.= 3 4 000 000 =.. .=. ==. =.= 3 5 000 000 ... =.. .=. ==. =.= 3 2 000 000 ..= =.= 3 3 000 000 ... ..= =.= 3 3 000 000 =.. ..= =.= 3 4 000 000 ... =.. ....
output:
Bob Bob Bob Bob Bob Bob Alice Bob Alice Bob Alice Alice Alice Alice Alice Alice Bob Bob Alice Bob
result:
ok 20 lines
Test #12:
score: 0
Accepted
time: 2ms
memory: 3268kb
input:
20 3 4 000 000 .=. ==. ..= =.= 3 5 000 000 ... .=. ==. ..= =.= 3 5 000 000 =.. .=. ==. ..= =.= 3 6 000 000 ... =.. .=. ==. ..= =.= 3 1 000 000 .== 3 2 000 000 ... .== 3 2 000 000 =.. .== 3 3 000 000 ... =.. .== 3 2 000 000 .=. .== 3 3 000 000 ... .=. .== 3 3 000 000 =.. .=. .== 3 4 000 000 ... =.. ....
output:
Alice Alice Alice Alice Bob Bob Alice Bob Alice Bob Alice Alice Bob Bob Bob Bob Bob Bob Alice Bob
result:
ok 20 lines
Test #13:
score: 0
Accepted
time: 0ms
memory: 3232kb
input:
20 3 2 000 000 ..= .== 3 3 000 000 ... ..= .== 3 3 000 000 =.. ..= .== 3 4 000 000 ... =.. ..= .== 3 3 000 000 .=. ..= .== 3 4 000 000 ... .=. ..= .== 3 4 000 000 =.. .=. ..= .== 3 5 000 000 ... =.. .=. ..= .== 3 3 000 000 ==. ..= .== 3 4 000 000 ... ==. ..= .== 3 4 000 000 =.. ==. ..= .== 3 5 000 0...
output:
Alice Bob Alice Alice Alice Alice Alice Alice Bob Bob Alice Alice Alice Bob Alice Alice Bob Bob Bob Bob
result:
ok 20 lines
Test #14:
score: 0
Accepted
time: 2ms
memory: 3292kb
input:
20 3 3 000 000 .=. =.= .== 3 4 000 000 ... .=. =.= .== 3 4 000 000 =.. .=. =.= .== 3 5 000 000 ... =.. .=. =.= .== 3 3 000 000 ==. =.= .== 3 4 000 000 ... ==. =.= .== 3 4 000 000 =.. ==. =.= .== 3 5 000 000 ... =.. ==. =.= .== 3 4 000 000 .=. ==. =.= .== 3 5 000 000 ... .=. ==. =.= .== 3 5 000 000 =...
output:
Bob Bob Alice Alice Bob Bob Bob Bob Bob Bob Bob Bob Bob Bob Alice Bob Alice Bob Alice Alice
result:
ok 20 lines
Test #15:
score: 0
Accepted
time: 0ms
memory: 3268kb
input:
8 3 4 000 000 ==. ..= =.= .== 3 5 000 000 ... ==. ..= =.= .== 3 5 000 000 =.. ==. ..= =.= .== 3 6 000 000 ... =.. ==. ..= =.= .== 3 5 000 000 .=. ==. ..= =.= .== 3 6 000 000 ... .=. ==. ..= =.= .== 3 6 000 000 =.. .=. ==. ..= =.= .== 3 7 000 000 ... =.. .=. ==. ..= =.= .==
output:
Bob Bob Bob Bob Bob Bob Bob Bob
result:
ok 8 lines
Test #16:
score: 0
Accepted
time: 3ms
memory: 3252kb
input:
20 10 815 4819325421 9470583705 .........= ........=. .......=.. .......=.= .......==. .......=== ......=... ......=..= ......=.=. ......=.== ......==.. ......===. ......==== .....=.... .....=..== .....=.=.. .....==... .....==..= .....==.=. .....==.== .....===.. .....===.= .....====. .....===== .......
output:
Alice Alice Alice Bob Alice Alice Alice Alice Alice Bob Alice Alice Bob Bob Alice Bob Alice Alice Alice Alice
result:
ok 20 lines
Test #17:
score: 0
Accepted
time: 7ms
memory: 3392kb
input:
20 10 7 9410870639 8237933369 .....=.=.= ...==.==.. ..===....= =..==..=.= =..==.=.== =.====.=.= ====.===.= 10 285 0225666838 4493031931 .......... .......=.. .......=== ......==.. ......==.= ......===. .....=.=.. .....=.=== .....==... .....==.== .....===.. ....=...=. ....=..=== ....=.=... ....=.=..=...
output:
Bob Bob Bob Bob Bob Bob Bob Bob Bob Bob Bob Bob Bob Bob Bob Bob Bob Bob Bob Bob
result:
ok 20 lines