QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#155791#4810. Add Onenhuang685WA 1ms3524kbC++202.8kb2023-09-02 05:48:522023-09-02 05:48:52

Judging History

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

  • [2023-09-02 05:48:52]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3524kb
  • [2023-09-02 05:48:52]
  • 提交

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);
  }
  g.push_back(std::bitset<N + 1>());
  g.back()[n] = true;
  g.push_back(std::bitset<N + 1>());
  for (int i = 0; i < (int)g.size() - 1; ++i) {
    bool good = true;
    if (g[i] == g[i + 1])
      continue;
    int cnt = 0;
    std::vector<std::bitset<N + 1>> h(g.begin(), g.begin() + i + 2);
    h.back()[n] = 0;
    for (int j = 0; j <= i + 1; ++j) {
      while (cnt < n && !h[j][cnt]) {
        if (!h[j][cnt]) {
          for (int k = j + 1; k <= i + 1; ++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 + 1; ++k) {
          if (h[k][n]) {
            good = false;
            break;
          }
        }
        break;
      }
      for (int k = j + 1; k <= i + 1; ++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: 100
Accepted
time: 0ms
memory: 3524kb

input:

4
1 2 1 2

output:

7

result:

ok 1 number(s): "7"

Test #2:

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

input:

5
1 2 3 4 5

output:

14

result:

ok 1 number(s): "14"

Test #3:

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

input:

6
1 2 4 7 15 31

output:

47

result:

ok 1 number(s): "47"

Test #4:

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

input:

5
41 40 50 11 36

output:

99

result:

ok 1 number(s): "99"

Test #5:

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

input:

6
10 40 60 2 44 47

output:

96

result:

ok 1 number(s): "96"

Test #6:

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

input:

6
46 25 39 47 23 60

output:

107

result:

ok 1 number(s): "107"

Test #7:

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

input:

6
56 90 61 63 56 23

output:

112

result:

ok 1 number(s): "112"

Test #8:

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

input:

7
8 83 78 19 36 6 22

output:

205

result:

ok 1 number(s): "205"

Test #9:

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

input:

7
23 23 22 78 2 29 88

output:

32

result:

ok 1 number(s): "32"

Test #10:

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

input:

7
109 80 14 27 9 45 24

output:

235

result:

ok 1 number(s): "235"

Test #11:

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

input:

7
144 152 137 143 145 139 183

output:

220

result:

ok 1 number(s): "220"

Test #12:

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

input:

7
189 270 119 372 240 144 153

output:

78

result:

ok 1 number(s): "78"

Test #13:

score: 0
Accepted
time: 0ms
memory: 3476kb

input:

7
4819 2494 1822 4759 2622 4111 2460

output:

7510

result:

ok 1 number(s): "7510"

Test #14:

score: 0
Accepted
time: 0ms
memory: 3476kb

input:

8
83 20 17 43 52 78 68 45

output:

145

result:

ok 1 number(s): "145"

Test #15:

score: 0
Accepted
time: 0ms
memory: 3432kb

input:

8
289 205 96 274 304 476 230 246

output:

925

result:

ok 1 number(s): "925"

Test #16:

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

input:

8
6866 7210 3474 9147 7676 7287 7339 7605

output:

14267

result:

ok 1 number(s): "14267"

Test #17:

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

input:

100
9080 7595 3488 1872 5813 1238 8798 2114 2047 6437 1719 5095 9036 2318 3453 8455 9441 7752 388 4695 1433 8253 1558 9068 8432 6751 5897 6993 7763 983 6741 9852 9812 5679 7980 8956 5905 7738 3091 3364 9630 5345 1574 255 5215 6863 9002 7324 6216 6471 2574 6026 5611 7998 1449 2191 4306 525 6534 1692 ...

output:

50142

result:

wrong answer 1st numbers differ - expected: '17374', found: '50142'