QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#537575 | #5250. Combination Locks | UESTC_DECAYALI# | WA | 0ms | 3780kb | C++20 | 1.7kb | 2024-08-30 16:05:48 | 2024-08-30 16:05:48 |
Judging History
answer
#include<cstdio>
#include<iostream>
#include<vector>
#define RI register int
#define CI const int&
using namespace std;
const int N=(1<<10)+5;
int t,n,m,ban[N],vis[N],pre[N]; char A[N],B[N]; vector <int> v[N];
inline int find(CI now,CI idx)
{
for (auto to:v[now])
{
if (vis[to]==idx) continue; vis[to]=idx;
if (!pre[to]||find(pre[to],idx)) return pre[to]=now,1;
}
return 0;
}
inline int work(void)
{
for (RI mask=0;mask<(1<<n);++mask)
{
v[mask].clear();
if (__builtin_popcount(mask)%2==1) continue;
if (ban[mask]) continue;
for (RI i=0;i<n;++i)
{
int nxt=mask^(1<<i);
if (ban[nxt]) continue;
v[mask].push_back(nxt);
//printf("%d -> %d\n",mask,nxt);
}
}
int match=0,idx=0;
for (RI i=0;i<(1<<n);++i) vis[i]=pre[i]=0;
for (RI mask=0;mask<(1<<n);++mask)
{
if (__builtin_popcount(mask)%2==1) continue;
match+=find(mask,++idx);
}
return match;
}
int main()
{
for (scanf("%d",&t);t;--t)
{
scanf("%d%d",&n,&m);
for (RI i=0;i<(1<<n);++i) ban[i]=0;
scanf("%s%s",A,B); int st=0;
for (RI i=0;i<n;++i) if (A[i]==B[i]) st|=(1<<i);
for (RI i=1;i<=m;++i)
{
scanf("%s",A); int mask=0;
for (RI j=0;j<n;++j) if (A[j]=='=') mask|=(1<<j);
ban[mask]=1;
}
int pre_match=work();
//printf("pre = %d\n",pre_match);
ban[st]=1;
int alt_match=work();
//printf("alt = %d\n",alt_match);
if (pre_match!=alt_match&&pre_match!=0) puts("Alice"); else puts("Bob");
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3780kb
input:
2 1 0 0 0 1 1 0 0 .
output:
Alice Bob
result:
ok 2 lines
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 3660kb
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 Alice Alice Alice Alice Bob Bob
result:
wrong answer 3rd lines differ - expected: 'Bob', found: 'Alice'