QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#644795#7900. Gifts from KnowledgeqiaochenWA 12ms3880kbC++142.8kb2024-10-16 15:29:412024-10-16 15:29:41

Judging History

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

  • [2024-10-16 15:29:41]
  • 评测
  • 测评结果:WA
  • 用时:12ms
  • 内存:3880kb
  • [2024-10-16 15:29:41]
  • 提交

answer

// Problem: G. Gifts from Knowledge
// Contest: Codeforces - The 2023 ICPC Asia Jinan Regional Contest (The 2nd Universal Cup. Stage 17: Jinan)
// URL: https://codeforces.com/gym/104901/problem/G
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef long long i64;
typedef array<int, 3> arr;
typedef pair<int, int> PII;

const int mod = 1E9 + 7;

struct DSU {
    std::vector<int> f, siz;
    
    DSU() {}
    DSU(int n) {
        init(n);
    }
    
    void init(int n) {
        f.resize(n);
        std::iota(f.begin(), f.end(), 0);
        siz.assign(n, 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)];
    }
};

int power(int a, i64 b, int p) {
    int res = 1;
    for (; b; b /= 2, a = 1LL * a * a % p) {
        if (b % 2) {
            res = 1LL * res * a % p;
        }
    }
    return res;
}

void solve() {
	int r, c;
	cin >> r >> c;	
	
	vector<string> s(r + 1);
	for (int i = 1; i <= r; i++) {
		cin >> s[i];
		s[i] = " " + s[i];
	}
	
	for (int j = 1; j <= (c + 1) / 2; j++) {
		int cnt = 0;
		for (int i = 1; i <= r; i++) {
			cnt += s[i][j] == '1';
			if (c & 1 && j != (c + 1) / 2) {
				cnt += s[i][c - j + 1] == '1';
			}
		}
		if (cnt > 2 || (c & 1 && j == (c + 1) / 2 && cnt >= 2)) {
			cout << 0 << "\n";
			return;
		}
	}

	DSU dsu(2 * r + 2);
	for (int j = 1; j <= c / 2; j++) {
		vector<int> v1, v2;
		for (int i = 1; i <= r; i++) {
			if (s[i][j] == '1') v1.push_back(i);
			if (s[i][c - j + 1] == '1') v2.push_back(i);
		}
		if (v1.size() == 1 && v2.size() == 1) {
			dsu.merge(v1.back(), v2.back());
			dsu.merge(v1.back() + r, v2.back() + r);	
		} else if (v1.empty() && v2.size() == 2) {
			dsu.merge(v2[0], v2[1] + r);
			dsu.merge(v2[0] + r, v2[1]);			
		} else if (v1.size() == 2 && v2.empty()) {
			dsu.merge(v1[0], v1[1] + r);
			dsu.merge(v1[0] + r, v1[1]);	
		}
	}
	
	for (int i = 1; i <= r; i++) {
		if (dsu.same(i, i + r)) {
			cout << 0 << "\n";
			return;
		}
	}
	
	int cnt = 0;
	for (int i = 1; i <= r; i++) {
		cnt += dsu.find(i) == i;
	}
	
	cout << power(2, cnt, mod) << "\n";
}

signed main() {
	cin.tie(nullptr)->ios::sync_with_stdio(false);
	
	int T;
	cin >> T;
	
	while (T--) {
		solve();
	}

	return 0;	
}

詳細信息

Test #1:

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

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: 12ms
memory: 3864kb

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: 12ms
memory: 3880kb

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 1590th numbers differ - expected: '0', found: '8192'