QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#603622#7900. Gifts from KnowledgeDoubeecatWA 0ms9708kbC++232.4kb2024-10-01 17:52:142024-10-01 17:52:15

Judging History

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

  • [2024-10-01 17:52:15]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:9708kb
  • [2024-10-01 17:52:14]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair <int,int>
#define endl '\n'
const int N = 2e6 + 10;
const ll mod=1e9+7;
vector <vector<int> > a;
int r,c;
char s[N];
int ck[N],tmp[N];
int p[N];
int find(int x){
    if(x!=p[x]){
        p[x]=find(p[x]);
    }
    return p[x];
}
ll qsm(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1)res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
void U(int a,int b){
    if(a!=b){
        p[a]=b;
    }
}
void solve() {
    cin >> r >> c;
    a.clear();
   
    for(int i=0;i<=2*r;i++){
        p[i]=i;
    }
    for(int i=0;i<=c;i++){
        ck[i]=tmp[i]=0;
    }
    a.resize(r+1);
    string pz;
    for (int i = 1;i <= r;++i) {
        cin >> s;
        a[i].resize(c+1);
        for (int j = 0;j < c;++j) {
            a[i][j+1] = s[j] - '0';
        }
    }

    for(int i=1;i<=c;i++){
        int cnt=0;
        for(int j=1;j<=r;j++){
            if(a[j][i]==1)cnt++;
            if(a[j][c-i+1]==1)cnt++;
        }
        if(cnt>2){
            cout<<0<<endl;
            return;
        }
    }
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            tmp[j]=ck[j];
        }
        for(int j=1;j<=c;j++){
            int x=j,y=c-j+1;
            if(y!=x&&a[i][j]&&tmp[y]){
                int pd1=tmp[y];
                int px=find(i),py=find(pd1);
                int px1=find(i+r),py1=find(pd1+r);

                if(px==py1||py==px1){
                    cout<<0<<endl;
                    return;
                }
                U(px,py);
                U(px1,py1);
            }else if(a[i][j]&&tmp[j]){
                cout<<j<<' '<<tmp[j]<<endl;
                int pd1=tmp[j];
                int px=find(i),py=find(pd1);
                int px1=find(i+r),py1=find(pd1+r);

                if(px==px1||py==py1||px==py){
                    cout<<0<<endl;
                    return;
                }
                U(px,py1);
                U(py,px1);
            }
            if(a[i][j])ck[j]=i;
        }
    }
    int cnt=0;
    for(int i=1;i<=2*r;i++){
        int pi=find(i);
        if(pi==i)cnt++;
    }
    cnt/=2;
    cout<<qsm(2,cnt)<<endl;
}
signed main() {
    ios::sync_with_stdio(false);
    int T;cin >> T;
    while (T--) solve(); 
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 9708kb

input:

3
3 5
01100
10001
00010
2 1
1
1
2 3
001
001

output:

4
0
3 1
2

result:

wrong answer 3rd numbers differ - expected: '2', found: '3'