QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#645456#7900. Gifts from KnowledgeChiTangWA 42ms3640kbC++173.6kb2024-10-16 18:29:092024-10-16 18:29:16

Judging History

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

  • [2024-10-16 18:29:16]
  • 评测
  • 测评结果:WA
  • 用时:42ms
  • 内存:3640kb
  • [2024-10-16 18:29:09]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int P = 1e9+7;

#define PII pair<int, int>
#define fi first
#define se second

const int N = 1e6 + 10;
int g[N][3];
int r, c;


vector<int> f, siz;

void init(int n)
{
    f.resize(n);
    iota(f.begin(), f.end(), 0); // 将每个节点的父节点都初始化为自己
    siz.assign(n, 1);            // 作为根节点的大小是1
}

int find(int x)
{
    while (x != f[x])
    {
        x = f[x] = f[f[x]];
    }
    return x;
}

bool same(int x, int y)
{
    return find(x) == find(y);
}

bool merge(int x, int y)
{
    x = find(x);
    y = find(y);
    if (x == y)
    {
        return false;
    }
    siz[x] += siz[y];
    f[y] = x;
    return true;
}

int size(int x)
{
    return siz[find(x)];
}
void solve()
{
    f.clear();
    siz.clear();
    cin >> r >> c;
    init((r + 1) * 2);
    vector<int> cnt(c + 10);
    vector<int> cnt2(c + 10);
    vector<int> vis((r+1)*2);
    set<int> p[c + 10];
    vector<vector<int>> v(r + 10, vector<int>(c + 10));
    for (int i = 1; i <= r; i++)
    {
        string s;
        cin >> s;
        for (int j = 0; j < c; j++)
        {
            v[i][j + 1] = s[j] - '0';
        }
        merge(i, i + r);
    }
    if (c % 2 == 1)
    {
        int nnum = 0;
        for (int i = 1; i <= r; i++)
        {
            if (v[i][c / 2 + 1] == 1)
                nnum++;
        }
        if (nnum >= 2)
        {
            cout <<0 << endl;
            return;
        }
    }

    for (int i = 1; i <= c / 2; i++)
    {
        int num = 0;
        for (int j = 1; j <= r; j++)
        {
            int cnttt=0;
            if (v[j][i] == 1)
            {
                cnttt++;
                num++;
                p[i].insert(j);
            }

            if (v[j][c - i + 1])
            {
                num++;
                p[i].insert(j);
                 cnttt++;
            }
            //说明两个1在不同列
            if(cnttt==2){
                cnt2[i]=1;
            }
        }

        if (num >= 3)
        {
            cout << 0 << endl;
            return;
        }

        cnt[i] = num;
        // cout<<i<<" "<<num<<endl;
    }
    for (int i = 1; i <= c / 2; i++)
    {
        if (cnt[i] == 2)
        {

            vector<int> a(2);
            int pos = 0;
            if (p[i].size() == 2)
            {
                // cout<<"yes"<<endl;
                for (auto x : p[i])
                {
                    a[pos] = x;
                    pos++;
                }
                if(cnt2[i]==1){
                    merge(a[0], a[1]+r);
                    merge(a[1], a[0]+r);
                }else{
                    merge(a[0], a[1]);
                    merge(a[0]+r, a[1]+r);
                }
                if(!vis[a[1]]){
                    vis[a[1]]++;
                }else{
                    cout<<0<<endl;
                    return ;
                }
               // merge(a[0], a[1]);
            }
        }
    }
    set<int> ans;
    for (int i = 1; i <= r*2; i++)
    {
        ans.insert(find(i));
        // cout<<find(i)<<" "<<i<<endl;
    }
    int res = 1;
    // cout<<ans.size()<<endl;
    for (int i = 0; i < ans.size(); i++)
    {
        res *= 2;
        res%=P;
    }
    cout << res << endl;
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    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: 3640kb

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: 36ms
memory: 3620kb

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: -100
Wrong Answer
time: 42ms
memory: 3596kb

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:

wrong answer 462nd numbers differ - expected: '8192', found: '0'