QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#155755 | #4810. Add One | nhuang685 | WA | 2ms | 3788kb | C++20 | 2.7kb | 2023-09-02 03:50:47 | 2023-09-02 03:50:47 |
Judging History
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'