QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#784238 | #7717. Bitsets | cppcppcpp3 | AC ✓ | 799ms | 10272kb | C++14 | 1.2kb | 2024-11-26 14:14:36 | 2024-11-26 14:14:41 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5;
const int inf=1e9+7;
inline int wrd(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+c-48,c=getchar();}return x*f;}
inline void write(long long x){if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+48);}
int n,m,q;
vector<vector<int>> a;
long long ans;
string s[2];
int ask(int x,int y){
if(x>y) swap(x,y);
int as(-1),l(0),r(m-1);
while(l<=r){
int mid=(l+r)>>1;
if(a[y][mid]<=x) as=mid,l=mid+1;
else r=mid-1;
}
return as+1;
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
cin>>n>>m,a.resize(n+1);
for(int i=1;i<=n;++i) a[i].resize(m,0);
for(int i=1;i<=n;++i){
int o=i&1; cin>>s[o];
if(i>1){
for(int j=0;j<m;++j){
if(s[o][j]==s[o^1][j]) a[i][j]=a[i-1][j];
else a[i][j]=i;
}
}else for(int j=0;j<m;++j) a[i][j]=1;
}
for(int i=1;i<=n;++i) sort(a[i].begin(),a[i].end());
cin>>q;
int x,y,z; cin>>x>>y>>z;
int l(1),r(n),as;
ans+=(as=ask(l,r)),--q;
while(q--){
l=(1ll*l*x+1ll*as*y+z)%n+1,r=(1ll*r*y+1ll*as*z+x)%n+1;
ans+=(as=ask(l,r));
}
cout<<ans<<"\n";
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3660kb
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: 3672kb
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: 3644kb
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: 0ms
memory: 3584kb
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: 0ms
memory: 3644kb
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: 3656kb
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: 3644kb
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: 0ms
memory: 3660kb
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: 0ms
memory: 3584kb
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: 3584kb
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: 3704kb
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: 0ms
memory: 3584kb
input:
1 1 0 1 2 2 2
output:
1
result:
ok 1 number(s): "1"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3708kb
input:
1 10 0010001000 1 2 2 2
output:
10
result:
ok 1 number(s): "10"
Test #14:
score: 0
Accepted
time: 0ms
memory: 3640kb
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: 3632kb
input:
100 100 0001000000000000100100100100000000100100100010000000000000000000000010000000000010001000000000000000 0000000000000000000000000000000000000000000000000000000000100000010000000010001000000100001000000000 000000000000000000000000000001000000010001000000000000000000000000000000100000000000001000...
output:
709
result:
ok 1 number(s): "709"
Test #16:
score: 0
Accepted
time: 7ms
memory: 4652kb
input:
500 500 1011111111111111111111111111011111110111111101111111111111111111111101111111111111111111111111111111011111111111111101111110101111111111111111101111111111111101110101111111110111111101111111111110111100111111101111111101011111111111111111111111111111111111111011111101111111111111111111111111...
output:
1394
result:
ok 1 number(s): "1394"
Test #17:
score: 0
Accepted
time: 29ms
memory: 7604kb
input:
1000 1000 00000000000000000000000000010000001110000000001000000100000000000000000000000000000000000001000000001000000000000000000000000000000000100010000000000000000000000000000000100000100100100100000000000000000000000000001100000000000001100000000000000000000000000000010000100000000000010000000000...
output:
21974
result:
ok 1 number(s): "21974"
Test #18:
score: 0
Accepted
time: 22ms
memory: 7712kb
input:
10000 100 1110111111110111111111111111111111011111111111011111111011111111111011111111111111111101111111111111 1110111101111111111111111111111111111111110111111111111111111111011111111101111111111111111111111111 1111110111111111111111111111011111111111111111111111111111111111111111111101111111111111...
output:
3586
result:
ok 1 number(s): "3586"
Test #19:
score: 0
Accepted
time: 21ms
memory: 7144kb
input:
100 10000 00110000010011110000100010110001110000001000010010110100001100010000011100100001111000000010000001000100101001000000010101001100000010100011011001000101001110000100100100100110000111010100000000101000001100011001101101011000010001110110000010010000000000000011101101100010110010100111000011...
output:
1046213
result:
ok 1 number(s): "1046213"
Test #20:
score: 0
Accepted
time: 30ms
memory: 7688kb
input:
5000 200 11000000100100000000000010001000000000000000000000000000010000000000000000000001000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 000000100000000000000000000000000010000000000000000000000010000000100000000000100000001000...
output:
170424
result:
ok 1 number(s): "170424"
Test #21:
score: 0
Accepted
time: 42ms
memory: 7764kb
input:
5000 200 00000000000000000000000000000000000000000000000000000000000000000000000000000000100000001000000000000000000000010010000000000000000000000000000000000000000000000000000000000000000000000000000000000000 000100000000000000001000010000000000000000000100000001000000000001000000000100000000000010...
output:
2499626
result:
ok 1 number(s): "2499626"
Test #22:
score: 0
Accepted
time: 163ms
memory: 7752kb
input:
5000 200 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000010000100000000000 000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000...
output:
35029587
result:
ok 1 number(s): "35029587"
Test #23:
score: 0
Accepted
time: 203ms
memory: 7692kb
input:
5000 200 00000000000000000000000000000000000000000010000000000000000000000000000000000000000000100000000010000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000 000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
16776
result:
ok 1 number(s): "16776"
Test #24:
score: 0
Accepted
time: 411ms
memory: 7408kb
input:
10 100000 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
2000000000000
result:
ok 1 number(s): "2000000000000"
Test #25:
score: 0
Accepted
time: 399ms
memory: 10272kb
input:
100000 10 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111...
output:
200000000
result:
ok 1 number(s): "200000000"
Test #26:
score: 0
Accepted
time: 271ms
memory: 7752kb
input:
5000 200 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
4000000000
result:
ok 1 number(s): "4000000000"
Test #27:
score: 0
Accepted
time: 373ms
memory: 7272kb
input:
200 5000 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
100000000000
result:
ok 1 number(s): "100000000000"
Test #28:
score: 0
Accepted
time: 799ms
memory: 7688kb
input:
5000 200 01011011001100110010110011101100111001100010110000011111011010111011010100111001011000110010011100101111110001010101101100100001111001011111110100011101011011111101010111111101000000000000110010010100 010110110011001100101100111011001110011000101100000111110110101110110101001110010110001100...
output:
2834691058
result:
ok 1 number(s): "2834691058"
Test #29:
score: 0
Accepted
time: 374ms
memory: 7044kb
input:
50 20000 111100111010100100001111000001011000000100101110101011000101000000001101100110000110110011001000101000000000000010111101001000100010100000000000010101100011110100000010011110110111100110111100101010100011111100000110100100011100100001001011110010010101010001010011001100000100001100011111010...
output:
177674291006
result:
ok 1 number(s): "177674291006"
Test #30:
score: 0
Accepted
time: 290ms
memory: 10192kb
input:
100000 10 1011010110 1000000000 0100111001 1010000100 1000111011 1011110101 1010011001 0110001010 1110010110 0000000001 0101110011 1100000111 0100101100 0111101111 1100101001 1001100110 1011110111 0111000010 1011101111 0011100010 0100100011 1111010111 0010000011 0001000100 0100101010 1001100001 1010...
output:
14
result:
ok 1 number(s): "14"
Test #31:
score: 0
Accepted
time: 320ms
memory: 7536kb
input:
999 999 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
19939999183
result:
ok 1 number(s): "19939999183"
Test #32:
score: 0
Accepted
time: 229ms
memory: 7532kb
input:
999 999 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
0
result:
ok 1 number(s): "0"