QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#648670#7900. Gifts from Knowledgefrankly6WA 4ms27432kbC++172.0kb2024-10-17 19:54:512024-10-17 19:54:51

Judging History

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

  • [2024-10-17 19:54:51]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:27432kb
  • [2024-10-17 19:54:51]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#define int long long
using namespace std;
const int p=1e9+7;
const int MX=1000010;

int T;
int fa[2*MX];
vector<int> num[MX];
int read()
{
    int r=0, f=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {r=r*10+ch-'0'; ch=getchar();}
    return r*f;
}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x, int y)
{
    // cout << "   merge:x=" << x << ", y=" << y << '\n';
    x=find(x), y=find(y);
    if(x>y) swap(x,y);
    fa[y]=x;
}
signed main()
{
    // freopen("testdata.in","r",stdin);
    T=read();
    while(T--)
    {
        int N=read(), M=read();
        // vector<vector<int>> v(N,vector<int>(M));
        for(int i=1;i<=2*N;i++) fa[i]=i;
        for(int i=1;i<=M;i++) num[i].clear();
        for(int i=1;i<=N;i++)
        {
            string s; cin >> s; s=" "+s;
            for(int j=1;j<=M;j++) 
                if(s[j]=='1') 
                {
                    num[j].emplace_back(i), 
                    num[M-j+1].emplace_back(-i);                    
                }
        }
        int ans=1;
        for(int i=1;i<=M;i++)
            if(num[i].size()>2) ans=0;
        for(int i=1;i<=M;i++)
        {
            if(num[i].size()!=2) continue;
            int p1=*num[i].begin(), p2=*num[i].rbegin();
            // if(p1==-p2) continue;
            if(p1*p2>0) merge(abs(p1),abs(p2)), merge(abs(p1)+N,abs(p2)+N);
            else merge(abs(p1),abs(p2)+N), merge(abs(p2),abs(p1)+N);
        }
        for(int i=1;i<=N;i++)
            if(find(i)==find(i+N)) ans=0;
        int tot=0;
        for(int i=1;i<=2*N;i++)
        {
            // cout << "i=" << i << ", fa[i]=" << find(i) << '\n';
            if(find(i)==i) tot++;
        }
        tot/=2;
        while(tot--) ans=ans*2%p;
        cout << ans << '\n';
    }
    return (0-0);
}

详细

Test #1:

score: 0
Wrong Answer
time: 4ms
memory: 27432kb

input:

3
3 5
01100
10001
00010
2 1
1
1
2 3
001
001

output:

0
0
2

result:

wrong answer 1st numbers differ - expected: '4', found: '0'