QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#499675#7900. Gifts from KnowledgeSaviorWA 25ms3764kbC++202.2kb2024-07-31 16:54:422024-07-31 16:54:42

Judging History

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

  • [2024-07-31 16:54:42]
  • 评测
  • 测评结果:WA
  • 用时:25ms
  • 内存:3764kb
  • [2024-07-31 16:54:42]
  • 提交

answer

#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
#define int long long
using ll=long long;
const int inf=1e9+7,N=50+5,mod=1e9+7;
typedef pair<int,int>P;

void solve(){
    int r,c;
    cin>>r>>c;
    vector<vector<char>>s(r+1,vector<char>(c+1));
    vector<int>cnt(c+1,0);
    vector<vector<int>>e(r+1);
    vector<vector<int>>tmp(c+1);
    for(int i=1;i<=r;i++)
        for(int j=1;j<=c;j++) {
            cin >> s[i][j], cnt[j] += (s[i][j] == '1');
            if(s[i][j]=='1') tmp[j].push_back(i);
        }
    for(int i=1;i<=c;i++){
        if(cnt[i]+cnt[1+c-i]>=3){
            cout<<0<<endl;
            return;
        }
        if(2*i==1+c&&cnt[i]>=2){
            cout<<0<<endl;
            return;
        }
    }
    for(int i=1;i<=r;i++){
        unordered_map<int,int>f1,f2;
        for(int j=1;j<=c;j++){
            if(s[i][j]=='1'){
                for(auto &it:tmp[j]){
                    if(it==i) continue;
                    f1[it]=1;
                    e[i].push_back(it);
                    //cout<<i<<' '<<it<<endl;
                }
                if(2*j==1+c) continue;
                for(auto &it:tmp[1+c-j]){
                    if(it==i) continue;
                    f2[it]=1;
                    e[i].push_back(it);
                    //cout<<i<<' '<<it<<endl;
                }
            }
        }
        for(auto &it:f2){
            if(f1.find(it.first)!=f1.end()){
                cout<<0<<endl;
                return;
            }
        }
        for(auto &it:f1){
            if(f2.find(it.first)!=f2.end()){
                cout<<0<<endl;
                return;
            }
        }
    }
    vector<int>v(r+1,0);
    int ans=1;
    function<void(int)>dfs=[&](int u){
        v[u]=1;
        for(auto &it:e[u]){
            if(v[it]) continue;
            dfs(it);
        }
    };
    for(int i=1;i<=r;i++){
        if(!v[i]){
            dfs(i);
            ans=ans*2%mod;
        }
    }
    cout<<ans<<endl;
    return;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int t=1;cin>>t;
    while(t--)solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3764kb

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: 0
Accepted
time: 18ms
memory: 3508kb

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:

1024
32768
2
32
32768
128
32
16
16
2
16384
16384
128
128
32768
8192
128
64
16384
2
4
2
4096
16
4096
1024
32768
32768
16384
8
128
2
16
4096
8192
32768
8192
8192
16
16384
16384
256
128
8
256
8
4096
512
2
4
32
32
2
64
512
1024
32768
32768
2
64
16384
16
8192
16
256
16
64
8192
8192
64
1024
2
32768
2
4
51...

result:

ok 15613 numbers

Test #3:

score: 0
Accepted
time: 20ms
memory: 3560kb

input:

15759
9 6
000000
000000
000000
000000
000000
000000
000000
000000
000000
5 15
010000000000000
000000000000000
000000000000000
000100000000000
000100000000000
14 12
000000000000
000000000000
000000000000
000000000000
000000000000
000000000000
000000000000
000000000000
000000000000
000000000000
000000...

output:

512
16
16384
512
1024
4096
32768
4
2
512
512
512
512
8
2
256
16
4096
512
64
16
4096
512
32
32768
8192
32
2048
128
16
4096
64
32768
256
32
16384
8
512
32
2048
8
16
1024
2048
128
64
32
8
512
8
8192
256
8192
32768
2
8
512
512
256
32
2
2048
8192
8
64
8
2
16384
32768
32768
1024
4096
16384
16384
128
256
4...

result:

ok 15759 numbers

Test #4:

score: -100
Wrong Answer
time: 25ms
memory: 3556kb

input:

15734
3 6
000101
010000
001110
5 7
0010010
1000000
0101000
0000000
0000000
10 9
000000000
100000000
000000000
000000000
000010000
000000001
000000000
000000000
000000000
000000000
5 14
10000000000000
00001001000000
00000100000000
00000000000000
00000100000000
5 14
00000000000000
00010000000100
00000...

output:

0
16
512
16
32
4096
0
256
0
0
0
0
4096
8
1024
128
8192
0
128
0
2
0
0
32
64
0
0
0
4096
64
8
8
32
128
64
4096
2
512
16384
4
2
0
0
32
0
4096
8
0
8192
256
256
64
0
32
0
32
0
256
4
16384
1024
4
0
16
256
0
2048
64
8
0
0
32768
2048
512
2048
2
0
8192
0
2
2048
16
512
256
1024
0
0
2
32
512
16384
0
32
1024
102...

result:

wrong answer 980th numbers differ - expected: '0', found: '2'