QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#83906 | #4810. Add One | Scintilla | TL | 2ms | 3532kb | C++14 | 1.3kb | 2023-03-04 08:39:58 | 2023-03-04 08:40:01 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, s, e) for (int i = s; i <= e; ++i)
#define drep(i, s, e) for (int i = s; i >= e; --i)
#define file(a) freopen(#a".in", "r", stdin), freopen(#a".out", "w", stdout)
#define pv(a) cout << #a << " = " << a << endl
#define pa(a, l, r) cout << #a " : "; rep(_, l, r) cout << a[_] << ' '; cout << endl
const int N = 1e6 + 10;
const int W = 61;
int read() {
int x = 0, f = 1; char c = getchar();
for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = -1;
for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - 48;
return x * f;
}
int n, a[N], s, ans;
namespace base {
int dat[N];
void clear() { fill(dat, dat + W, 0); }
void ins(int x) {
drep(i, __lg(x), 0) if (x >> i & 1) {
if (dat[i]) x ^= dat[i];
else { dat[i] = x; break; }
}
}
bool ask(int x) {
drep(i, __lg(x), 0) if (x >> i & 1) x ^= dat[i];
return !x;
}
}
signed main() {
n = read();
rep(i, 1, n) a[i] = read(), s ^= a[i];
rep(i, 0, W - 1) if (~s >> i & 1) {
rep(j, 1, n) base::ins(a[j] & ((1ll << i + 1) - 1));
if (base::ask((1ll << i) - 1)) ans = s ^ ((1ll << i + 1) - 1);
base::clear();
}
printf("%lld\n", ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3532kb
input:
4 1 2 1 2
output:
7
result:
ok 1 number(s): "7"
Test #2:
score: 0
Accepted
time: 2ms
memory: 3488kb
input:
5 1 2 3 4 5
output:
14
result:
ok 1 number(s): "14"
Test #3:
score: 0
Accepted
time: 2ms
memory: 3504kb
input:
6 1 2 4 7 15 31
output:
47
result:
ok 1 number(s): "47"
Test #4:
score: 0
Accepted
time: 2ms
memory: 3432kb
input:
5 41 40 50 11 36
output:
99
result:
ok 1 number(s): "99"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3520kb
input:
6 10 40 60 2 44 47
output:
96
result:
ok 1 number(s): "96"
Test #6:
score: -100
Time Limit Exceeded
input:
6 46 25 39 47 23 60