oj.uz

Submission #905030

# Submission time Handle Problem Language Result Execution time Memory
905030 2024-01-12T13:07:50 Z LucaLucaM Intergalactic ship (IZhO19_xorsum) C++17
17 / 100
 2000 ms 7768 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstring>
#warning That's the baby, that's not my baby
#define int long long

typedef long long ll;

const int mod = 1e9 + 7;
const int NMAX = 1000;
const int VMAX = 128;

struct Update {
  int l, r, x;
};

int cnt[VMAX][VMAX];
ll newCnt[VMAX][VMAX];
ll ways[NMAX][NMAX];

/// cnt[x][y] =def= pt cate subset uri am a[i] = x, a[j] = y?

#define debug(x) #x << " = " << x
bool matters[NMAX];

signed main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);

  int n;
  std::cin >> n;
  std::vector<int> a(n);
  for (int i = 0; i < n; i++) {
    std::cin >> a[i];
  }

  for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {
      ways[i][j] = (i + 1) * (n - j);
    }
  }

  int q;
  std::cin >> q;

  std::vector<Update> Q(q);

  for (auto &[l, r, v] : Q) {
    std::cin >> l >> r >> v;
    --l, --r;
    matters[l] = true;
    matters[r] = true;
  }

  ll answer = 0;

  for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {
      if (i != j && !matters[j] && !matters[j - 1]) {
        for (int x = 0; x < VMAX; x++) {
          for (int y = 0; y < VMAX; y++) {
            newCnt[x][y ^ a[j - 1] ^ a[j]] += cnt[x][y];
          }
        }
        for (int x = 0; x < VMAX; x++) {
          for (int y = 0; y < VMAX; y++) {
            cnt[x][y] = newCnt[x][y];
            newCnt[x][y] = 0;
          }
        }
      } else {
        memset(cnt, 0, sizeof(cnt));
        cnt[a[i]][a[j]] = 1;
        for (auto &[l, r, v] : Q) {
          for (int x = 0; x < VMAX; x++) {
            for (int y = 0; y < VMAX; y++) {
              int newX = x;
              int newY = y;
              if (l <= i && i  <= r) {
                newX ^= v;
              }
              if (l <= j && j <= r) {
                newY ^= v;
              }
              newCnt[x][y] += cnt[x][y];
              newCnt[newX][newY] += cnt[x][y];
            }
          }
          for (int x = 0; x < VMAX; x++) {
            for (int y = 0; y < VMAX; y++) {
              cnt[x][y] = newCnt[x][y] % mod;
              newCnt[x][y] = 0;
            }
          }
        }
      }

      for (int x = 0; x < VMAX; x++) {
        for (int y = 0; y < VMAX; y++) {
          if (i == j) {
            if (x == y) {
              answer += (ll) cnt[x][x] * x % mod * x % mod * ways[i][j] % mod;
            }
          } else {
            answer += (ll) 2 * cnt[x][y] * x % mod * y % mod * ways[i][j] % mod;
          }
        }
      }
    }
  }

  std::cout << answer % mod;

  return 0;
}

Compilation message

xorsum.cpp:6:2: warning: #warning That's the baby, that's not my baby [-Wcpp]
    6 | #warning That's the baby, that's not my baby
      |  ^~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 2 ms 600 KB Output is correct
3 Correct 35 ms 732 KB Output is correct
4 Correct 34 ms 600 KB Output is correct
5 Correct 21 ms 604 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 2 ms 600 KB Output is correct
3 Correct 35 ms 732 KB Output is correct
4 Correct 34 ms 600 KB Output is correct
5 Correct 21 ms 604 KB Output is correct
6 Correct 1164 ms 2852 KB Output is correct
7 Correct 972 ms 2860 KB Output is correct
8 Correct 1196 ms 2860 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2029 ms 5212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2017 ms 7768 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 483 ms 2844 KB Output is correct
2 Correct 435 ms 2848 KB Output is correct
3 Correct 491 ms 2840 KB Output is correct

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 483 ms 2844 KB Output is correct
2 Correct 435 ms 2848 KB Output is correct
3 Correct 491 ms 2840 KB Output is correct
4 Execution timed out 2008 ms 2904 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 2 ms 600 KB Output is correct
3 Correct 35 ms 732 KB Output is correct
4 Correct 34 ms 600 KB Output is correct
5 Correct 21 ms 604 KB Output is correct
6 Correct 1164 ms 2852 KB Output is correct
7 Correct 972 ms 2860 KB Output is correct
8 Correct 1196 ms 2860 KB Output is correct
9 Correct 483 ms 2844 KB Output is correct
10 Correct 435 ms 2848 KB Output is correct
11 Correct 491 ms 2840 KB Output is correct
12 Execution timed out 2048 ms 2652 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 2 ms 600 KB Output is correct
3 Correct 35 ms 732 KB Output is correct
4 Correct 34 ms 600 KB Output is correct
5 Correct 21 ms 604 KB Output is correct
6 Correct 1164 ms 2852 KB Output is correct
7 Correct 972 ms 2860 KB Output is correct
8 Correct 1196 ms 2860 KB Output is correct
9 Correct 483 ms 2844 KB Output is correct
10 Correct 435 ms 2848 KB Output is correct
11 Correct 491 ms 2840 KB Output is correct
12 Execution timed out 2008 ms 2904 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 2 ms 600 KB Output is correct
3 Correct 35 ms 732 KB Output is correct
4 Correct 34 ms 600 KB Output is correct
5 Correct 21 ms 604 KB Output is correct
6 Correct 1164 ms 2852 KB Output is correct
7 Correct 972 ms 2860 KB Output is correct
8 Correct 1196 ms 2860 KB Output is correct
9 Execution timed out 2029 ms 5212 KB Time limit exceeded
10 Halted 0 ms 0 KB -