QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#155041#4810. Add Onenhuang685WA 24ms18600kbC++202.2kb2023-09-01 07:22:242023-09-01 07:22:25

Judging History

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

  • [2023-09-01 07:22:25]
  • 评测
  • 测评结果:WA
  • 用时:24ms
  • 内存:18600kb
  • [2023-09-01 07:22:24]
  • 提交

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 = 60;
constexpr int N = 1'000'000;

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 = base;
  for (int i = 0; i < LG; ++i) {
    std::bitset<N + 1> v;
    for (int j = 0; j < n; ++j)
      if ((1ll << i) & a[j])
        v[j] = 1;
    v[n] = 1;
    g.push_back(v);

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

詳細信息

Test #1:

score: 100
Accepted
time: 23ms
memory: 18304kb

input:

4
1 2 1 2

output:

7

result:

ok 1 number(s): "7"

Test #2:

score: 0
Accepted
time: 24ms
memory: 18600kb

input:

5
1 2 3 4 5

output:

14

result:

ok 1 number(s): "14"

Test #3:

score: 0
Accepted
time: 22ms
memory: 18120kb

input:

6
1 2 4 7 15 31

output:

47

result:

ok 1 number(s): "47"

Test #4:

score: -100
Wrong Answer
time: 13ms
memory: 18332kb

input:

5
41 40 50 11 36

output:

31

result:

wrong answer 1st numbers differ - expected: '99', found: '31'