QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#620022#7900. Gifts from KnowledgeqmqcbhcWA 14ms38592kbC++201.7kb2024-10-07 16:19:392024-10-07 16:19:40

Judging History

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

  • [2024-10-07 16:19:40]
  • 评测
  • 测评结果:WA
  • 用时:14ms
  • 内存:38592kb
  • [2024-10-07 16:19:39]
  • 提交

answer

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

const int INF=0x3f3f3f3f;
const ll N=1e6+5;
const ll mod=1e9+7;

ll t,n,m;
string str[N];
ll a[2*N];
vector<ll> vis[N];

void fio(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

void init_set(int n){
	for(int i=0; i<=2*n+5; i++){
		a[i]=i;
	}
}

int find_set(int x){
	if(x != a[x]) a[x]=find_set(a[x]); //压缩路径
	return a[x];
}

void merge_set(int x, int y){
	x = find_set(x);
	y = find_set(y);
	if(x!=y) a[x]=a[y]; //x以y为父
}

signed main()
{
	fio();
	cin >> t;
	while(t--){
		cin >> n >> m;
		init_set(n);
		for(int i=1; i<=m; i++){
			vis[i].clear();
		}
		for(int i=1; i<=n; i++){
			//str[i].clear();
			cin >> str[i];
		}
		//i是不翻,i+n翻
		ll flag=0;
		for(int i=1; i<=n; i++){
			for(int j=0; j<m; j++){
				if(str[i][j]=='1'){
					vis[j+1].push_back(i);
				}
			}
		}
		
		for(int i=1; i<=m; i++){
			//cout << vis[i].size() << endl;
			if(vis[i].size()+vis[m-i+1].size()>2){
				flag=1;
			}
			if(vis[i].size()==0) continue;
			if(vis[i].size()==1 && vis[m-i+1].size()==1){
				merge_set(vis[i][0],vis[m-i+1][0]);
				merge_set(vis[i][0]+n,vis[m-i+1][0]+n);
			}
			else if(vis[i].size()==2){
				merge_set(vis[i][0]+n,vis[i][1]);
				merge_set(vis[i][0],vis[i][1]+n);
			}
		}
		for(int i=1; i<=n; i++){
			if(find_set(i)==find_set(i+n)) flag=1;
		}
		if(flag){
			cout << 0 << endl;
			continue;
		}
		ll ans=1;
		ll cc=0;
		for(int i=1; i<=2*n; i++){
			if(a[i]==i){
				cc++;
			}
		}
		cc/=2;
		for(int i=1; i<=cc; i++){
			ans%=mod;
			ans*=2;
			ans%=mod;
		}
		cout << ans%mod;
		if(t!=1) cout << endl;
	}
	return 0;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 5ms
memory: 37996kb

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: 14ms
memory: 38592kb

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:

wrong answer 15612th numbers differ - expected: '2', found: '22'