QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#155755#4810. Add Onenhuang685WA 2ms3788kbC++202.7kb2023-09-02 03:50:472023-09-02 03:50:47

Judging History

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

  • [2023-09-02 03:50:47]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3788kb
  • [2023-09-02 03:50: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) {
      g.push_back(v);
      break;
    }
    v[n] = 1;
    g.push_back(v);
  }
  for (int i = 0; i < g.size() - 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: 100
Accepted
time: 2ms
memory: 3788kb

input:

4
1 2 1 2

output:

7

result:

ok 1 number(s): "7"

Test #2:

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

input:

5
1 2 3 4 5

output:

14

result:

ok 1 number(s): "14"

Test #3:

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

input:

6
1 2 4 7 15 31

output:

47

result:

ok 1 number(s): "47"

Test #4:

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

input:

5
41 40 50 11 36

output:

99

result:

ok 1 number(s): "99"

Test #5:

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

input:

6
10 40 60 2 44 47

output:

96

result:

ok 1 number(s): "96"

Test #6:

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

input:

6
46 25 39 47 23 60

output:

107

result:

ok 1 number(s): "107"

Test #7:

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

input:

6
56 90 61 63 56 23

output:

112

result:

ok 1 number(s): "112"

Test #8:

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

input:

7
8 83 78 19 36 6 22

output:

205

result:

ok 1 number(s): "205"

Test #9:

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

input:

7
23 23 22 78 2 29 88

output:

32

result:

ok 1 number(s): "32"

Test #10:

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

input:

7
109 80 14 27 9 45 24

output:

235

result:

ok 1 number(s): "235"

Test #11:

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

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: 3728kb

input:

7
189 270 119 372 240 144 153

output:

78

result:

ok 1 number(s): "78"

Test #13:

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

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: 3520kb

input:

8
83 20 17 43 52 78 68 45

output:

145

result:

ok 1 number(s): "145"

Test #15:

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

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: 3748kb

input:

8
6866 7210 3474 9147 7676 7287 7339 7605

output:

14267

result:

ok 1 number(s): "14267"

Test #17:

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

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:

17374

result:

ok 1 number(s): "17374"

Test #18:

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

input:

200
5427 2263 8443 3141 4775 842 1756 8604 3074 4508 9608 3344 9356 6102 710 7484 6543 7718 7441 7920 9928 8282 3941 1347 6908 4386 4269 4723 5797 1447 2381 305 7275 2568 9250 3113 8438 9273 1280 6609 5225 9253 3732 7991 2975 8690 9299 9009 63 2852 4309 2316 2948 9798 3731 790 9770 5527 1775 8388 44...

output:

27971

result:

ok 1 number(s): "27971"

Test #19:

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

input:

200
11526 12520 983 17606 861 12619 10319 11496 18084 8341 10236 7895 19999 5599 416 12109 16336 9173 15715 1418 8492 13373 8142 6881 13158 16435 9429 593 15751 8793 1476 19166 6627 10965 7368 1295 15449 8063 14489 9651 13570 944 11544 10602 10342 6543 6385 1108 19358 4365 4990 18004 11530 4237 1253...

output:

45265

result:

ok 1 number(s): "45265"

Test #20:

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

input:

500
4445 583 3305 855 5165 3564 1977 1573 903 3999 3272 8905 8160 4359 5982 8912 7850 5050 6441 5436 4598 3644 685 2529 4467 2012 1541 8348 4624 1495 4558 5195 3169 6737 5622 3837 4693 7760 1530 8909 6326 7449 612 6472 2347 9855 8008 4469 9859 5498 6014 2939 4554 3016 1947 1863 8316 532 1407 6723 78...

output:

4127

result:

wrong answer 1st numbers differ - expected: '28641', found: '4127'