QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#155753#4810. Add Onenhuang685WA 0ms3432kbC++202.6kb2023-09-02 03:49:472023-09-02 03:49:48

Judging History

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

  • [2023-09-02 03:49:48]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3432kb
  • [2023-09-02 03:49:47]
  • 提交

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 = 5;

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);
  }
  for (int i = 0; i < LG - 1; ++i) {
    bool good = true;
    if (g[i] == g[i + 1])
      break;
    int cnt = 0;
    std::vector<std::bitset<N + 1>> h(g.begin(), g.begin() + i + 1);
    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[k][n]) {
            good = false;
            break;
          }
        }
        break;
      }
      for (int k = j + 1; k <= i; ++k)
        if (h[k][cnt])
          h[k] ^= h[j];
      cnt++;
    }
    if (good)
      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: 0
Wrong Answer
time: 0ms
memory: 3432kb

input:

4
1 2 1 2

output:

63

result:

wrong answer 1st numbers differ - expected: '7', found: '63'