QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#783763#7717. BitsetsRDFZchenyyRE 76ms404752kbC++142.5kb2024-11-26 11:42:502024-11-26 11:42:52

Judging History

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

  • [2024-11-26 11:42:52]
  • 评测
  • 测评结果:RE
  • 用时:76ms
  • 内存:404752kb
  • [2024-11-26 11:42:50]
  • 提交

answer

#include<bits/stdc++.h>

using ll=long long;

#define MAXN 100005

int n,m,k,l,r;
ll ans,x,y,z;
std::string s[MAXN];
int f[MAXN][105];
ll a[2000005],b[2000005],q[2000005];
int g[10005][10005];

int main(){
    std::ios::sync_with_stdio(false);

    std::cin>>n>>m;
    for(int i=1;i<=n;i++){
        std::cin>>s[i];
    }
    std::cin>>k;
    std::cin>>x>>y>>z;

    if(n<=10000){
    // if(false){
        for(int i=1;i<=n;i++){
            for(int j=0;j<m;j++){
                if(i==1){
                    int p=i;
                    while(p<=n){
                        if(s[p][j]!=s[i][j]){
                            break;
                        }
                        ++p;
                    }
                    g[i][i]++;
                    g[i][p]--;
                    g[p][i]--;
                    g[p][p]++;
                }else if(s[i-1][j]!=s[i][j]){
                    int p=i;
                    while(p<=n){
                        if(s[p][j]!=s[i][j]){
                            break;
                        }
                        ++p;
                    }
                    g[i][i]++;
                    g[i][p]--;
                    g[p][i]--;
                    g[p][p]++;
                }
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                g[i][j]=g[i][j]+g[i-1][j]+g[i][j-1]-g[i-1][j-1];
            }
        }
        for(int i=1;i<=k;i++){
            if(i==1){
                a[1]=1,b[1]=n;
            }else{
                a[i]=(a[i-1]*x+q[i-1]*y+z)%n+1;
                b[i]=(b[i-1]*y+q[i-1]*z+x)%n+1;
            }
            q[i]=g[a[i]][b[i]];
            ans+=q[i];
        }
        std::cout<<ans<<'\n';
    }else{
        for(int i=1;i<=n-1;i++){
            for(int j=0;j<m;j++){
                f[i][j]=(s[i][j]!=s[i+1][j]);
                f[i][j]+=f[i-1][j];
            }
        }
        for(int i=1;i<=k;i++){
            if(i==1){
                a[1]=1,b[1]=n;
            }else{
                a[i]=(a[i-1]*x+q[i-1]*y+z)%n+1;
                b[i]=(b[i-1]*y+q[i-1]*z+x)%n+1;
            }
            l=std::min(a[i],b[i]),r=std::max(a[i],b[i]);
            if(l==r) q[i]=m;
            else{
                for(int j=0;j<m;j++){
                    q[i]+=((f[r-1][j]-f[l-1][j])?0:1);
                }
            }
            ans+=q[i];
        }
        std::cout<<ans<<'\n';
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4 10
1010110101
0101111001
1101101101
1011010000
4
10 5 4

output:

9

result:

ok 1 number(s): "9"

Test #2:

score: 0
Accepted
time: 2ms
memory: 14812kb

input:

6 3
110
011
010
100
101
111
5
7 5 5

output:

3

result:

ok 1 number(s): "3"

Test #3:

score: 0
Accepted
time: 0ms
memory: 13376kb

input:

10 10
1100101001
0011100101
1100001110
0101011100
1001011010
0010101101
1001011011
0010110000
1001100111
0010101000
10
11 11 11

output:

26

result:

ok 1 number(s): "26"

Test #4:

score: 0
Accepted
time: 2ms
memory: 13984kb

input:

6 7
1101001
1000110
0010000
1110001
1110100
0001011
15
7 5 7

output:

30

result:

ok 1 number(s): "30"

Test #5:

score: 0
Accepted
time: 2ms
memory: 13528kb

input:

10 13
0101011101010
0100000011001
0001101010111
1101000111100
1001110000110
0110011000110
1101101110100
0101101110011
0000100011100
1100010110100
20
11 11 11

output:

60

result:

ok 1 number(s): "60"

Test #6:

score: 0
Accepted
time: 2ms
memory: 13332kb

input:

12 15
010010101101011
010000100100011
110011010100011
111011101010111
101110111010100
100000111011011
010100001101100
001011010111100
000011011100010
101100101001010
010000111101111
110100011011000
25
11 13 13

output:

0

result:

ok 1 number(s): "0"

Test #7:

score: 0
Accepted
time: 0ms
memory: 16272kb

input:

15 16
1111010001110110
1111100101111111
1111111111001010
0010100111111001
1011011000001000
1111000101000000
1001101100100011
0010111000001110
0011111000010001
1000011111011111
1101000111000001
0010010100001011
1110001111111010
0011100110100001
0101110010101101
30
13 13 17

output:

448

result:

ok 1 number(s): "448"

Test #8:

score: 0
Accepted
time: 2ms
memory: 14196kb

input:

13 15
001100110010010
011100110100111
111100000000110
111000011101010
111100011001010
100111101001001
000110010111101
100101000000100
011010001000000
101001100011100
011110111111000
010110111100111
110010010100110
35
13 13 11

output:

0

result:

ok 1 number(s): "0"

Test #9:

score: 0
Accepted
time: 2ms
memory: 13352kb

input:

11 9
110101001
001010011
000100101
110011000
110101110
001001100
110100110
100110000
100010111
110110000
111100000
40
13 11 13

output:

47

result:

ok 1 number(s): "47"

Test #10:

score: 0
Accepted
time: 0ms
memory: 16476kb

input:

10 18
010111010010010001
111010101000100111
011010111100011001
000010000111001111
101010010000110100
001110000101111101
010101011011000100
111011110001010010
111010101101000000
100101010111101100
45
11 11 11

output:

353

result:

ok 1 number(s): "353"

Test #11:

score: 0
Accepted
time: 0ms
memory: 13952kb

input:

11 17
01100000011010100
11100001111000101
10011100111011011
10011110010011000
10110110111110010
01001001101111000
11010101101101110
01101101110001110
11101000000101001
00000110000001000
10001111001100010
50
13 11 13

output:

228

result:

ok 1 number(s): "228"

Test #12:

score: 0
Accepted
time: 2ms
memory: 13300kb

input:

1 1
0
1
2 2 2

output:

1

result:

ok 1 number(s): "1"

Test #13:

score: 0
Accepted
time: 2ms
memory: 14696kb

input:

1 10
0010001000
1
2 2 2

output:

10

result:

ok 1 number(s): "10"

Test #14:

score: 0
Accepted
time: 3ms
memory: 14820kb

input:

10 1
0
0
0
0
1
0
0
0
1
0
1
11 11 11

output:

0

result:

ok 1 number(s): "0"

Test #15:

score: 0
Accepted
time: 3ms
memory: 18516kb

input:

100 100
0001000000000000100100100100000000100100100010000000000000000000000010000000000010001000000000000000
0000000000000000000000000000000000000000000000000000000000100000010000000010001000000100001000000000
000000000000000000000000000001000000010001000000000000000000000000000000100000000000001000...

output:

709

result:

ok 1 number(s): "709"

Test #16:

score: 0
Accepted
time: 0ms
memory: 35116kb

input:

500 500
1011111111111111111111111111011111110111111101111111111111111111111101111111111111111111111111111111011111111111111101111110101111111111111111101111111111111101110101111111110111111101111111111110111100111111101111111101011111111111111111111111111111111111111011111101111111111111111111111111...

output:

1394

result:

ok 1 number(s): "1394"

Test #17:

score: 0
Accepted
time: 4ms
memory: 53488kb

input:

1000 1000
00000000000000000000000000010000001110000000001000000100000000000000000000000000000000000001000000001000000000000000000000000000000000100010000000000000000000000000000000100000100100100100000000000000000000000000001100000000000001100000000000000000000000000000010000100000000000010000000000...

output:

21974

result:

ok 1 number(s): "21974"

Test #18:

score: 0
Accepted
time: 76ms
memory: 404752kb

input:

10000 100
1110111111110111111111111111111111011111111111011111111011111111111011111111111111111101111111111111
1110111101111111111111111111111111111111110111111111111111111111011111111101111111111111111111111111
1111110111111111111111111111011111111111111111111111111111111111111111111101111111111111...

output:

3586

result:

ok 1 number(s): "3586"

Test #19:

score: 0
Accepted
time: 10ms
memory: 18764kb

input:

100 10000
00110000010011110000100010110001110000001000010010110100001100010000011100100001111000000010000001000100101001000000010101001100000010100011011001000101001110000100100100100110000111010100000000101000001100011001101101011000010001110110000010010000000000000011101101100010110010100111000011...

output:

1046213

result:

ok 1 number(s): "1046213"

Test #20:

score: 0
Accepted
time: 28ms
memory: 214060kb

input:

5000 200
11000000100100000000000010001000000000000000000000000000010000000000000000000001000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000100000000000000000000000000010000000000000000000000010000000100000000000100000001000...

output:

170424

result:

ok 1 number(s): "170424"

Test #21:

score: 0
Accepted
time: 43ms
memory: 234092kb

input:

5000 200
00000000000000000000000000000000000000000000000000000000000000000000000000000000100000001000000000000000000000010010000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000100000000000000001000010000000000000000000100000001000000000001000000000100000000000010...

output:

2499626

result:

ok 1 number(s): "2499626"

Test #22:

score: -100
Runtime Error

input:

5000 200
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000010000100000000000
000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000...

output:


result: