QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#632861 | #7717. Bitsets | memset0 | AC ✓ | 1696ms | 20916kb | C++23 | 1.7kb | 2024-10-12 14:05:37 | 2024-10-12 14:05:37 |
Judging History
answer
#include <bits/stdc++.h>
#define sz(x) ((int)(x).size())
#define all(x) begin(x), end(x)
#ifdef memset0
#define log(...) fprintf(stderr, __VA_ARGS__)
#else
#define endl '\n'
#define log(...) (void(0))
#endif
using namespace std;
using ll = long long;
using lf = long double;
using ull = unsigned long long;
const int N = 1e5 + 9;
int n, m, k, x, y, z, s[N], lastans;
ll sum;
string buffer;
vector<int> a[N], vec[N];
int solve(int l, int r) {
// assert(l <= r);
int ans;
if (l == r) {
ans = m;
} else {
ans = upper_bound(all(vec[r]), l) - vec[r].begin();
}
log("solve l=%d r=%d ==> %d\n", l, r, ans);
lastans = ans;
sum += ans;
return ans;
}
int main() {
#ifdef memset0
freopen("B.in", "r", stdin);
#endif
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> buffer;
a[i].resize(sz(buffer));
for (int j = 0; j < m; j++) {
a[i][j] = buffer[j] == '1';
}
}
for (int j = 0; j < m; j++) {
int lst = -1;
for (int i = 1; i <= n; i++) {
if (i == 1 || a[i][j] != a[i - 1][j]) {
lst = i;
}
vec[i].push_back(lst);
}
}
for (int i = 1; i <= n; i++) {
sort(all(vec[i]));
// for (int x : vec[i]) log("%d, ", x);
// log("\n");
}
cin >> k;
cin >> x >> y >> z;
int a = 1, b = n;
solve(1, n);
for (int i = 2; i <= k; i++) {
a = ((ll)a * x + (ll)lastans * y + z) % n + 1;
b = ((ll)b * y + (ll)lastans * z + x) % n + 1;
solve(min(a, b), max(a, b));
}
cout << sum << endl;
}
/*
1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 2, 2, 2, 2, 2, 2,
1, 1, 1, 2, 2, 2, 2, 3, 3, 3,
1, 2, 3, 4, 4, 4, 4, 4, 4, 4,
solve l=1 r=4 ==> 1
solve l=3 r=3 ==> 10
solve l=2 r=3 ==> 7
solve l=1 r=3 ==> 3
21
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3724kb
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: 1ms
memory: 3652kb
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: 2ms
memory: 5708kb
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: 5720kb
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: 5704kb
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: 5716kb
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: 3664kb
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: 1ms
memory: 3680kb
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: 3732kb
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: 3600kb
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: 2ms
memory: 5724kb
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: 1ms
memory: 3596kb
input:
1 1 0 1 2 2 2
output:
1
result:
ok 1 number(s): "1"
Test #13:
score: 0
Accepted
time: 0ms
memory: 5720kb
input:
1 10 0010001000 1 2 2 2
output:
10
result:
ok 1 number(s): "10"
Test #14:
score: 0
Accepted
time: 1ms
memory: 3604kb
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: 2ms
memory: 5804kb
input:
100 100 0001000000000000100100100100000000100100100010000000000000000000000010000000000010001000000000000000 0000000000000000000000000000000000000000000000000000000000100000010000000010001000000100001000000000 000000000000000000000000000001000000010001000000000000000000000000000000100000000000001000...
output:
709
result:
ok 1 number(s): "709"
Test #16:
score: 0
Accepted
time: 9ms
memory: 5432kb
input:
500 500 1011111111111111111111111111011111110111111101111111111111111111111101111111111111111111111111111111011111111111111101111110101111111111111111101111111111111101110101111111110111111101111111111110111100111111101111111101011111111111111111111111111111111111111011111101111111111111111111111111...
output:
1394
result:
ok 1 number(s): "1394"
Test #17:
score: 0
Accepted
time: 33ms
memory: 11360kb
input:
1000 1000 00000000000000000000000000010000001110000000001000000100000000000000000000000000000000000001000000001000000000000000000000000000000000100010000000000000000000000000000000100000100100100100000000000000000000000000001100000000000001100000000000000000000000000000010000100000000000010000000000...
output:
21974
result:
ok 1 number(s): "21974"
Test #18:
score: 0
Accepted
time: 47ms
memory: 13344kb
input:
10000 100 1110111111110111111111111111111111011111111111011111111011111111111011111111111111111101111111111111 1110111101111111111111111111111111111111110111111111111111111111011111111101111111111111111111111111 1111110111111111111111111111011111111111111111111111111111111111111111111101111111111111...
output:
3586
result:
ok 1 number(s): "3586"
Test #19:
score: 0
Accepted
time: 26ms
memory: 12920kb
input:
100 10000 00110000010011110000100010110001110000001000010010110100001100010000011100100001111000000010000001000100101001000000010101001100000010100011011001000101001110000100100100100110000111010100000000101000001100011001101101011000010001110110000010010000000000000011101101100010110010100111000011...
output:
1046213
result:
ok 1 number(s): "1046213"
Test #20:
score: 0
Accepted
time: 39ms
memory: 13020kb
input:
5000 200 11000000100100000000000010001000000000000000000000000000010000000000000000000001000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 000000100000000000000000000000000010000000000000000000000010000000100000000000100000001000...
output:
170424
result:
ok 1 number(s): "170424"
Test #21:
score: 0
Accepted
time: 55ms
memory: 12960kb
input:
5000 200 00000000000000000000000000000000000000000000000000000000000000000000000000000000100000001000000000000000000000010010000000000000000000000000000000000000000000000000000000000000000000000000000000000000 000100000000000000001000010000000000000000000100000001000000000001000000000100000000000010...
output:
2499626
result:
ok 1 number(s): "2499626"
Test #22:
score: 0
Accepted
time: 248ms
memory: 12956kb
input:
5000 200 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000010000100000000000 000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000...
output:
35029587
result:
ok 1 number(s): "35029587"
Test #23:
score: 0
Accepted
time: 348ms
memory: 15112kb
input:
5000 200 00000000000000000000000000000000000000000010000000000000000000000000000000000000000000100000000010000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000 000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
16776
result:
ok 1 number(s): "16776"
Test #24:
score: 0
Accepted
time: 703ms
memory: 11572kb
input:
10 100000 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
2000000000000
result:
ok 1 number(s): "2000000000000"
Test #25:
score: 0
Accepted
time: 1696ms
memory: 20864kb
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: 610ms
memory: 12956kb
input:
5000 200 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
4000000000
result:
ok 1 number(s): "4000000000"
Test #27:
score: 0
Accepted
time: 667ms
memory: 13088kb
input:
200 5000 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
100000000000
result:
ok 1 number(s): "100000000000"
Test #28:
score: 0
Accepted
time: 515ms
memory: 15052kb
input:
5000 200 01011011001100110010110011101100111001100010110000011111011010111011010100111001011000110010011100101111110001010101101100100001111001011111110100011101011011111101010111111101000000000000110010010100 010110110011001100101100111011001110011000101100000111110110101110110101001110010110001100...
output:
2834691058
result:
ok 1 number(s): "2834691058"
Test #29:
score: 0
Accepted
time: 569ms
memory: 12784kb
input:
50 20000 111100111010100100001111000001011000000100101110101011000101000000001101100110000110110011001000101000000000000010111101001000100010100000000000010101100011110100000010011110110111100110111100101010100011111100000110100100011100100001001011110010010101010001010011001100000100001100011111010...
output:
177674291006
result:
ok 1 number(s): "177674291006"
Test #30:
score: 0
Accepted
time: 658ms
memory: 20916kb
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: 540ms
memory: 11372kb
input:
999 999 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
19939999183
result:
ok 1 number(s): "19939999183"
Test #32:
score: 0
Accepted
time: 316ms
memory: 11404kb
input:
999 999 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
0
result:
ok 1 number(s): "0"