QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#155737#4810. Add Onenhuang685WA 2ms3660kbC++202.9kb2023-09-02 03:07:172023-09-02 03:07:18

Judging History

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

  • [2023-09-02 03:07:18]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3660kb
  • [2023-09-02 03:07:17]
  • 提交

answer

/**
 * @file qoj4810-1.cpp
 * @author n685
 * @brief
 * @date 2023-08-31
 *
 *
 */
#include <bits/stdc++.h>

#ifdef LOCAL
std::ifstream cin;
std::ofstream cout;
using std::cerr;
#else
using std::cin;
using std::cout;
#define cerr                                                                   \
  if (false)                                                                   \
  std::cerr
#endif

#ifdef LOCAL
#include "dd/debug.h"
#define dbg(...) lineInfo(__LINE__, #__VA_ARGS__), dbg1(__VA_ARGS__)
#define dbgR(...) lineInfo(__LINE__, #__VA_ARGS__ " R"), dbg2(__VA_ARGS__)
#define dbgP(p, ...) lineInfo(__LINE__, #__VA_ARGS__ " P"), dbg3(p, __VA_ARGS__)
#define dbgRP(p, ...)                                                          \
  lineInfo(__LINE__, #__VA_ARGS__ " RP"), dbg4(p, __VA_ARGS__)
void nline() { cerr << '\n'; }
#else
#define dbg(...) 42
#define dbgR(...) 4'242
#define dbgP(...) 420
#define dbgRP(...) 420'420
void nline() {}
#endif

constexpr int LG = 61;
// constexpr int N = 1'000'000;
constexpr int N = 10;

int main() {
#ifdef LOCAL
  cin.open("input.txt");
  cout.rdbuf()->pubsetbuf(0, 0);
  cout.open("output.txt");
#else
  cin.tie(nullptr)->sync_with_stdio(false);
#endif

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

  std::vector<std::bitset<N + 1>> g;
  int64_t ans = std::max(base, base ^ 1);
  for (int i = 0; i < LG; ++i) {
    std::bitset<N + 1> v;
    bool good = false;
    for (int j = 0; j < n; ++j) {
      if ((1ll << i) & a[j]) {
        v[j] = 1;
        good = true;
      }
    }
    if (!good)
      break;
    v[n] = 1;
    g.push_back(v);

    int cnt = 0;
    std::vector<std::bitset<N + 1>> h = g;
    for (int j = 0; j <= i; ++j) {
      while (cnt < n && !h[j][cnt]) {
        if (!h[j][cnt]) {
          for (int k = j + 1; k <= i; ++k) {
            if (h[k][cnt]) {
              std::swap(h[j], h[k]);
              break;
            }
          }
        }
        if (!h[j][cnt])
          cnt++;
      }
      if (cnt == n) {
        for (int k = j; k <= i; ++k) {
          if (h[j][n]) {
            good = false;
            break;
          }
        }
        break;
      }
      for (int k = 0; k <= i; ++k)
        if (k != j && h[k][cnt])
          h[k] ^= h[j];
      cnt++;
    }
    if (good) {
      // bool ggg = true;
      // for (int j = 0; j <= i; ++j) {
      //   bool gg = false;
      //   for (int k = 0; k < n; ++k) {
      //     if (h[j][k]) {
      //       gg = true;
      //       break;
      //     }
      //   }
      //   if (!gg && h[j][n]) {
      //     ggg = false;
      //     break;
      //   }
      // }
      // if (ggg)
      ans = std::max(ans, (int64_t)(base ^ ((1ll << (i + 2)) - 1)));
    }
  }
  cout << ans << '\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3628kb

input:

4
1 2 1 2

output:

7

result:

ok 1 number(s): "7"

Test #2:

score: 0
Accepted
time: 2ms
memory: 3508kb

input:

5
1 2 3 4 5

output:

14

result:

ok 1 number(s): "14"

Test #3:

score: 0
Accepted
time: 1ms
memory: 3628kb

input:

6
1 2 4 7 15 31

output:

47

result:

ok 1 number(s): "47"

Test #4:

score: 0
Accepted
time: 1ms
memory: 3600kb

input:

5
41 40 50 11 36

output:

99

result:

ok 1 number(s): "99"

Test #5:

score: 0
Accepted
time: 1ms
memory: 3660kb

input:

6
10 40 60 2 44 47

output:

96

result:

ok 1 number(s): "96"

Test #6:

score: 0
Accepted
time: 1ms
memory: 3628kb

input:

6
46 25 39 47 23 60

output:

107

result:

ok 1 number(s): "107"

Test #7:

score: -100
Wrong Answer
time: 1ms
memory: 3564kb

input:

6
56 90 61 63 56 23

output:

176

result:

wrong answer 1st numbers differ - expected: '112', found: '176'