QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#155791 | #4810. Add One | nhuang685 | WA | 1ms | 3524kb | C++20 | 2.8kb | 2023-09-02 05:48:52 | 2023-09-02 05:48:52 |
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)
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';
}
详细
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'