QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#628013#7717. BitsetsPlentyOfPenalty#WA 1ms5704kbC++201.8kb2024-10-10 18:12:172024-10-10 18:12:18

Judging History

你现在查看的是最新测评结果

  • [2024-10-10 18:12:18]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5704kb
  • [2024-10-10 18:12:17]
  • 提交

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

*/

详细

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'