QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#608723#7900. Gifts from KnowledgeDoubeecatRE 39ms9848kbC++202.9kb2024-10-04 01:38:542024-10-04 01:38:54

Judging History

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

  • [2024-10-04 01:38:54]
  • 评测
  • 测评结果:RE
  • 用时:39ms
  • 内存:9848kb
  • [2024-10-04 01:38:54]
  • 提交

answer

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cmath>
#include <queue>
using namespace std;
#define ll long long
#define pii pair <int,int>
#define endl '\n'
#define mp make_pair
const int N = 2e6 + 10;
const ll mod=1e9+7;
vector <vector<int> > a;
vector <bool> vis;
vector <int> col;
vector <vector<pii > > G;
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;
}
bool dfs(int x) {
    //cout << x << " " << col[x] << endl;
    vis[x] = 1;
    bool flag = 1;
    for (auto [y,w] : G[x]) {
        if (!vis[y]) {
            if (w == 1) col[y] = col[x];
            else col[y] = 3 - col[x];
            dfs(y);
        } else {
            int now = 0;
            if (w == 1) {
                now = col[y] == col[x];
            } else {
                now = col[y] == (3 - col[x]);
            }
            if (!now) flag = 0;
        }
    }
    return flag;
}
void solve() {
    cin >> r >> c;
    a.clear();G.clear();vis.clear();col.clear();
    for(int i=1;i<=2*r;i++){
        ck[i]=0;tmp[i] = 0;
        p[i]=i;
    }
    a.resize(r+1);
    vis.resize(r+1);
    G.resize(r+1);
    col.resize(r+1);
    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];
                G[i].push_back(mp(pd1,1));
                G[pd1].push_back(mp(i,1));
                //printf("(%d,%d)=%d\n",i,pd1,1);
            }else if(a[i][j]&&tmp[j]){
                int pd1=tmp[j];
                G[i].push_back(mp(pd1,2));
                G[pd1].push_back(mp(i,2));
                //printf("(%d,%d)=%d\n",i,pd1,2);
            }
            if(a[i][j])ck[j]=i;
        }
    }
    int cnt=0,qwq=0;
    for(int i=1;i<=r;i++){
        if (!vis[i]) {
            col[i] = 1;
            bool flag = dfs(i);
            //printf("%d:%d\n",i,flag);
            if (flag) ++cnt;
           // else qwq = 1;
        }
    }
    if (!qwq) cout<<qsm(2,cnt)<<endl;
    else cout << "-1\n";
}
signed main() {
   // ios::sync_with_stdio(false);
    int T;cin >> T;
    while (T--) solve(); 
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 9780kb

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: 39ms
memory: 9848kb

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
Runtime Error

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: