QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#628013 | #7717. Bitsets | PlentyOfPenalty# | WA | 1ms | 5704kb | C++20 | 1.8kb | 2024-10-10 18:12:17 | 2024-10-10 18:12:18 |
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) {
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 <= n; 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: 5704kb
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: 0ms
memory: 3700kb
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: -100
Wrong Answer
time: 0ms
memory: 5632kb
input:
6 7 1101001 1000110 0010000 1110001 1110100 0001011 15 7 5 7
output:
12
result:
wrong answer 1st numbers differ - expected: '30', found: '12'