QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#155041 | #4810. Add One | nhuang685 | WA | 24ms | 18600kb | C++20 | 2.2kb | 2023-09-01 07:22:24 | 2023-09-01 07:22:25 |
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 = 60;
constexpr int N = 1'000'000;
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 = base;
for (int i = 0; i < LG; ++i) {
std::bitset<N + 1> v;
for (int j = 0; j < n; ++j)
if ((1ll << i) & a[j])
v[j] = 1;
v[n] = 1;
g.push_back(v);
int cnt = 0;
std::vector<std::bitset<N + 1>> h = g;
bool g = true;
for (int j = 0; j <= i; ++j) {
if (!h[j][cnt]) {
for (int k = j + 1; k <= i; ++k) {
if (h[k][cnt]) {
std::swap(h[j], h[k]);
break;
}
}
}
while (cnt < n && !h[j][cnt])
cnt++;
if (cnt == n) {
g = false;
break;
}
for (int k = j + 1; k <= i; ++k)
if (h[k][cnt])
h[k] ^= h[j];
}
if (g)
ans = std::max(ans, (int64_t)(base ^ ((1ll << (i + 2)) - 1)));
}
cout << ans << '\n';
}
详细
Test #1:
score: 100
Accepted
time: 23ms
memory: 18304kb
input:
4 1 2 1 2
output:
7
result:
ok 1 number(s): "7"
Test #2:
score: 0
Accepted
time: 24ms
memory: 18600kb
input:
5 1 2 3 4 5
output:
14
result:
ok 1 number(s): "14"
Test #3:
score: 0
Accepted
time: 22ms
memory: 18120kb
input:
6 1 2 4 7 15 31
output:
47
result:
ok 1 number(s): "47"
Test #4:
score: -100
Wrong Answer
time: 13ms
memory: 18332kb
input:
5 41 40 50 11 36
output:
31
result:
wrong answer 1st numbers differ - expected: '99', found: '31'