QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#155737 | #4810. Add One | nhuang685 | WA | 2ms | 3660kb | C++20 | 2.9kb | 2023-09-02 03:07:17 | 2023-09-02 03:07:18 |
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 = 10;
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);
int cnt = 0;
std::vector<std::bitset<N + 1>> h = g;
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[j][n]) {
good = false;
break;
}
}
break;
}
for (int k = 0; k <= i; ++k)
if (k != j && h[k][cnt])
h[k] ^= h[j];
cnt++;
}
if (good) {
// bool ggg = true;
// for (int j = 0; j <= i; ++j) {
// bool gg = false;
// for (int k = 0; k < n; ++k) {
// if (h[j][k]) {
// gg = true;
// break;
// }
// }
// if (!gg && h[j][n]) {
// ggg = false;
// break;
// }
// }
// if (ggg)
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: 3628kb
input:
4 1 2 1 2
output:
7
result:
ok 1 number(s): "7"
Test #2:
score: 0
Accepted
time: 2ms
memory: 3508kb
input:
5 1 2 3 4 5
output:
14
result:
ok 1 number(s): "14"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3628kb
input:
6 1 2 4 7 15 31
output:
47
result:
ok 1 number(s): "47"
Test #4:
score: 0
Accepted
time: 1ms
memory: 3600kb
input:
5 41 40 50 11 36
output:
99
result:
ok 1 number(s): "99"
Test #5:
score: 0
Accepted
time: 1ms
memory: 3660kb
input:
6 10 40 60 2 44 47
output:
96
result:
ok 1 number(s): "96"
Test #6:
score: 0
Accepted
time: 1ms
memory: 3628kb
input:
6 46 25 39 47 23 60
output:
107
result:
ok 1 number(s): "107"
Test #7:
score: -100
Wrong Answer
time: 1ms
memory: 3564kb
input:
6 56 90 61 63 56 23
output:
176
result:
wrong answer 1st numbers differ - expected: '112', found: '176'