QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#678336#7900. Gifts from Knowledgexxk2006WA 32ms5680kbC++233.0kb2024-10-26 14:40:502024-10-26 14:41:28

Judging History

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

  • [2024-10-26 14:41:28]
  • 评测
  • 测评结果:WA
  • 用时:32ms
  • 内存:5680kb
  • [2024-10-26 14:40:50]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define ULL unsigned long long
#define Enter putchar('\n')
#define spc putchar(' ')
#define pb push_back
#define fi first
#define se second
inline void read(int &num){num=0;int f=1;char ch=getchar();while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){num=(num<<1)+(num<<3)+(ch^48);ch=getchar();}num*=f;}
inline void lread(long long &num){num=0;int f=1;char ch=getchar();while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){num=(num<<1)+(num<<3)+(ch^48);ch=getchar();}num*=f;}
void print(long long num){if(num<0){putchar('-');num=-num;}if(num>9){print(num/10);}putchar((num%10)^48);}
vector<bool> a[1000009];
int ct[1000009];
int fa[2000009];
bool g[1000009];
const int p=1e9+7;
int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
int main(){
    int T,n,m;
    char ch;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)a[i].clear(),fa[i]=i,fa[i+n]=i+n,g[i]=0;
        for(int i=1;i<=m;i++)ct[i]=0;
        for(int i=1;i<=n;i++){
            a[i].pb(1);
            for(int j=1;j<=m;j++){
                scanf(" %c",&ch);
                if(ch=='1'){
                    a[i].pb(1);
                    ++ct[j];
                }
                else a[i].pb(0);
            }
        }
        if((m&1)&&ct[(m+1)>>1]>=2){
            puts("0");
            continue;
        }
        bool flag=1;
        int st=0,fi=-1,se=-1,x,y;
        for(int i=1;i<=(m>>1);i++){
            if(ct[i]+ct[m-i+1]>=3){
                flag=0;
                break;
            }
            if(ct[i]+ct[m-i+1]==2){
                for(int j=1;j<=n;j++){
                    if(a[j][i]){
                        if(fi==-1)fi=j,x=1;
                        else se=j,y=1;
                    }
                    if(a[j][m-i+1]){
                        if(fi==-1)fi=j,x=2;
                        else se=j,y=2;
                    }
                }
                if(fi!=se){
                    g[fi]=g[se]=1;
                    if(x==y){
                        if(find(fi)==find(se)||find(fi+n)==find(se+n)){
                            flag=0;
                            break;
                        }
                        fa[find(fi)]=find(se+n);
                        fa[find(fi+n)]=find(se);
                    }
                    else{
                        if(find(fi)==find(se+n)||find(fi+n)==find(se)){
                            flag=0;
                            break;
                        }
                        fa[find(fi)]=find(se);
                        fa[find(fi+n)]=find(se+n);                        
                    }
                }
            }
        }
        if(!flag){
            puts("0");
            continue;
        }
        LL ans=2;
        for(int i=1;i<=n;i++)if(!g[i])ans=(ans*2)%p;
        print(ans),Enter;
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 5680kb

input:

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

output:

4
0
2

result:

ok 3 number(s): "4 0 2"

Test #2:

score: -100
Wrong Answer
time: 32ms
memory: 5680kb

input:

15613
10 10
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
15 8
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
1 5
00000
5 9
000000000
000000000
0000...

output:

2048
65536
4
64
65536
256
64
32
32
4
32768
32768
256
256
65536
16384
256
128
32768
4
8
4
8192
32
8192
2048
65536
65536
32768
16
256
4
32
8192
16384
65536
16384
16384
32
32768
32768
512
256
16
512
16
8192
1024
4
8
64
64
4
128
1024
2048
65536
65536
4
128
32768
32
16384
32
512
32
128
16384
16384
128
20...

result:

wrong answer 1st numbers differ - expected: '1024', found: '2048'