QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #783761 | #7717. Bitsets | RDFZchenyy | ML | 3ms | 95268kb | C++14 | 2.5kb | 2024-11-26 11:42:14 | 2024-11-26 11:42:16 |
Judging History
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];
ll 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: 3ms
memory: 14712kb
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: 0ms
memory: 14888kb
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: 16404kb
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: 16028kb
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: 16284kb
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: 0ms
memory: 13364kb
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: 2ms
memory: 15708kb
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: 15988kb
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: 13452kb
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: 16204kb
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: 15700kb
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: 14748kb
input:
1 1 0 1 2 2 2
output:
1
result:
ok 1 number(s): "1"
Test #13:
score: 0
Accepted
time: 2ms
memory: 14364kb
input:
1 10 0010001000 1 2 2 2
output:
10
result:
ok 1 number(s): "10"
Test #14:
score: 0
Accepted
time: 0ms
memory: 14716kb
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: 0ms
memory: 21432kb
input:
100 100 0001000000000000100100100100000000100100100010000000000000000000000010000000000010001000000000000000 0000000000000000000000000000000000000000000000000000000000100000010000000010001000000100001000000000 000000000000000000000000000001000000010001000000000000000000000000000000100000000000001000...
output:
709
result:
ok 1 number(s): "709"
Test #16:
score: 0
Accepted
time: 3ms
memory: 53260kb
input:
500 500 1011111111111111111111111111011111110111111101111111111111111111111101111111111111111111111111111111011111111111111101111110101111111111111111101111111111111101110101111111110111111101111111111110111100111111101111111101011111111111111111111111111111111111111011111101111111111111111111111111...
output:
1394
result:
ok 1 number(s): "1394"
Test #17:
score: 0
Accepted
time: 3ms
memory: 95268kb
input:
1000 1000 00000000000000000000000000010000001110000000001000000100000000000000000000000000000000000001000000001000000000000000000000000000000000100010000000000000000000000000000000100000100100100100000000000000000000000000001100000000000001100000000000000000000000000000010000100000000000010000000000...
output:
21974
result:
ok 1 number(s): "21974"
Test #18:
score: -100
Memory Limit Exceeded
input:
10000 100 1110111111110111111111111111111111011111111111011111111011111111111011111111111111111101111111111111 1110111101111111111111111111111111111111110111111111111111111111011111111101111111111111111111111111 1111110111111111111111111111011111111111111111111111111111111111111111111101111111111111...
output:
3586