QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#783864 | #7717. Bitsets | yiming564 | AC ✓ | 488ms | 17236kb | C++14 | 1.6kb | 2024-11-26 12:04:01 | 2024-11-26 12:04:10 |
Judging History
answer
#include <bits/extc++.h>
#define inline __always_inline
template <typename T> inline void chkmin(T &x, const T &y) { if (x > y) x = y; }
template <typename T> inline void read(T &x)
{
char ch;
for (ch = getchar(); !isdigit(ch); ch = getchar());
for (x = 0; isdigit(ch); ch = getchar()) x = x * 10 + (ch - '0');
}
inline void digit(int &x) { for (x = getchar(); !isdigit(x); x = getchar()); x -= '0'; }
const int MaxM = 1e5 + 5, MaxN = MaxM, MaxQ = 2e6 + 5;
int n, m, q, **len;
std::vector<std::vector<bool>> s;
namespace gen
{
int x, y, z, a, b, l, r;
inline void init()
{
read(x), read(y), read(z);
a = l = 1, b = r = n;
}
inline void gen(int ans)
{
a = (1l * a * x + 1l * ans * y + z) % n + 1;
b = (1l * b * y + 1l * ans * z + x) % n + 1;
l = std::min(a, b), r = std::max(a, b);
}
} // namespace gen
using gen::l, gen::r;
int main()
{
read(n), read(m);
s.resize(n + 1);
for (int i = 1; i <= n; i++)
s[i].resize(m + 1);
len = (int **)calloc(n + 1, 8);
for (int i = 1; i <= n; i++)
len[i] = (int *)calloc(m + 1, 4);
for (int i = 1; i <= n; i++)
for (int j = 1, x; j <= m; j++)
digit(x), s[i][j] = x;
for (int i = n - 1; i; i--)
for (int j = 1; j <= m; j++)
len[i][j] = s[i][j] == s[i + 1][j] ? len[i + 1][j] + 1 : 0;
for (int i = n - 1; i; i--)
std::sort(len[i] + 1, len[i] + m + 1);
read(q);
gen::init();
int64_t sum = 0; int ans = 0;
do
{
sum += ans = len[l] + m + 1 - std::lower_bound(len[l] + 1, len[l] + m + 1, r - l);
gen::gen(ans);
} while (--q);
printf("%ld", sum);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3700kb
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: 3760kb
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: 3840kb
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: 3836kb
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: 3840kb
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: 3760kb
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: 3840kb
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: 3876kb
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: 3824kb
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: 3812kb
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: 3824kb
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: 3832kb
input:
1 1 0 1 2 2 2
output:
1
result:
ok 1 number(s): "1"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3912kb
input:
1 10 0010001000 1 2 2 2
output:
10
result:
ok 1 number(s): "10"
Test #14:
score: 0
Accepted
time: 0ms
memory: 3820kb
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: 1ms
memory: 3824kb
input:
100 100 0001000000000000100100100100000000100100100010000000000000000000000010000000000010001000000000000000 0000000000000000000000000000000000000000000000000000000000100000010000000010001000000100001000000000 000000000000000000000000000001000000010001000000000000000000000000000000100000000000001000...
output:
709
result:
ok 1 number(s): "709"
Test #16:
score: 0
Accepted
time: 8ms
memory: 4860kb
input:
500 500 1011111111111111111111111111011111110111111101111111111111111111111101111111111111111111111111111111011111111111111101111110101111111111111111101111111111111101110101111111110111111101111111111110111100111111101111111101011111111111111111111111111111111111111011111101111111111111111111111111...
output:
1394
result:
ok 1 number(s): "1394"
Test #17:
score: 0
Accepted
time: 27ms
memory: 7940kb
input:
1000 1000 00000000000000000000000000010000001110000000001000000100000000000000000000000000000000000001000000001000000000000000000000000000000000100010000000000000000000000000000000100000100100100100000000000000000000000000001100000000000001100000000000000000000000000000010000100000000000010000000000...
output:
21974
result:
ok 1 number(s): "21974"
Test #18:
score: 0
Accepted
time: 29ms
memory: 8212kb
input:
10000 100 1110111111110111111111111111111111011111111111011111111011111111111011111111111111111101111111111111 1110111101111111111111111111111111111111110111111111111111111111011111111101111111111111111111111111 1111110111111111111111111111011111111111111111111111111111111111111111111101111111111111...
output:
3586
result:
ok 1 number(s): "3586"
Test #19:
score: 0
Accepted
time: 26ms
memory: 7788kb
input:
100 10000 00110000010011110000100010110001110000001000010010110100001100010000011100100001111000000010000001000100101001000000010101001100000010100011011001000101001110000100100100100110000111010100000000101000001100011001101101011000010001110110000010010000000000000011101101100010110010100111000011...
output:
1046213
result:
ok 1 number(s): "1046213"
Test #20:
score: 0
Accepted
time: 30ms
memory: 8020kb
input:
5000 200 11000000100100000000000010001000000000000000000000000000010000000000000000000001000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 000000100000000000000000000000000010000000000000000000000010000000100000000000100000001000...
output:
170424
result:
ok 1 number(s): "170424"
Test #21:
score: 0
Accepted
time: 43ms
memory: 8196kb
input:
5000 200 00000000000000000000000000000000000000000000000000000000000000000000000000000000100000001000000000000000000000010010000000000000000000000000000000000000000000000000000000000000000000000000000000000000 000100000000000000001000010000000000000000000100000001000000000001000000000100000000000010...
output:
2499626
result:
ok 1 number(s): "2499626"
Test #22:
score: 0
Accepted
time: 217ms
memory: 8012kb
input:
5000 200 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000010000100000000000 000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000...
output:
35029587
result:
ok 1 number(s): "35029587"
Test #23:
score: 0
Accepted
time: 333ms
memory: 8084kb
input:
5000 200 00000000000000000000000000000000000000000010000000000000000000000000000000000000000000100000000010000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000 000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
16776
result:
ok 1 number(s): "16776"
Test #24:
score: 0
Accepted
time: 345ms
memory: 7476kb
input:
10 100000 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
2000000000000
result:
ok 1 number(s): "2000000000000"
Test #25:
score: 0
Accepted
time: 488ms
memory: 17236kb
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: 347ms
memory: 8088kb
input:
5000 200 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
4000000000
result:
ok 1 number(s): "4000000000"
Test #27:
score: 0
Accepted
time: 362ms
memory: 7880kb
input:
200 5000 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
100000000000
result:
ok 1 number(s): "100000000000"
Test #28:
score: 0
Accepted
time: 344ms
memory: 8008kb
input:
5000 200 01011011001100110010110011101100111001100010110000011111011010111011010100111001011000110010011100101111110001010101101100100001111001011111110100011101011011111101010111111101000000000000110010010100 010110110011001100101100111011001110011000101100000111110110101110110101001110010110001100...
output:
2834691058
result:
ok 1 number(s): "2834691058"
Test #29:
score: 0
Accepted
time: 385ms
memory: 7868kb
input:
50 20000 111100111010100100001111000001011000000100101110101011000101000000001101100110000110110011001000101000000000000010111101001000100010100000000000010101100011110100000010011110110111100110111100101010100011111100000110100100011100100001001011110010010101010001010011001100000100001100011111010...
output:
177674291006
result:
ok 1 number(s): "177674291006"
Test #30:
score: 0
Accepted
time: 457ms
memory: 17212kb
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: 333ms
memory: 7880kb
input:
999 999 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
19939999183
result:
ok 1 number(s): "19939999183"
Test #32:
score: 0
Accepted
time: 377ms
memory: 7880kb
input:
999 999 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
0
result:
ok 1 number(s): "0"