QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#89574#5250. Combination Lockssky3142AC ✓7ms3392kbC++201.7kb2023-03-20 16:43:142023-03-20 16:43:18

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-20 16:43:18]
  • 评测
  • 测评结果:AC
  • 用时:7ms
  • 内存:3392kb
  • [2023-03-20 16:43:14]
  • 提交

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