QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#645411 | #7900. Gifts from Knowledge | ChiTang | WA | 27ms | 3592kb | C++17 | 3.4kb | 2024-10-16 18:14:10 | 2024-10-16 18:14:12 |
Judging History
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);
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);
}
// 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: 1ms
memory: 3512kb
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: 20ms
memory: 3592kb
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: 27ms
memory: 3540kb
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 2380th numbers differ - expected: '0', found: '4'