QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#746903 | #7937. Fast XORting | Mine_King | WA | 61ms | 5648kb | C++14 | 1.0kb | 2024-11-14 15:49:52 | 2024-11-14 15:49:53 |
Judging History
answer
// 長い夜の終わりを信じながら
// Think twice, code once.
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;
int n, a[1 << 18], ans1, ans2;
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
for (int i = __lg(n) - 1; i >= 0; i--) {
int len = 1 << (i + 1);
int res0 = 0, res1 = 0;
for (int j = 0; j < n; j += len) {
vector<int> vec[2];
for (int k = j; k < j + len; k++) {
if (!(a[k] >> i & 1)) res0 += vec[1].size();
else res1 += vec[0].size();
vec[a[k] >> i & 1].push_back(a[k]);
}
for (int k = 0; k < len / 2; k++) a[j + k] = vec[0][k];
for (int k = 0; k < len / 2; k++) a[j + len / 2 + k] = vec[1][k];
}
ans1 += res0, ans2 += min(res0, res1);
}
printf("%d\n", min(ans1, ans2 + 1));
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3748kb
input:
8 0 1 3 2 5 4 7 6
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
8 2 0 1 3 4 5 6 7
output:
2
result:
ok 1 number(s): "2"
Test #3:
score: -100
Wrong Answer
time: 61ms
memory: 5648kb
input:
262144 47482 131703 90418 122675 166494 247529 196154 16950 66501 50357 246808 25929 10418 50538 26955 151884 63776 58023 20073 26544 74785 44064 41836 148543 87920 54172 3270 131495 130960 112122 167229 215767 77499 195004 21391 11039 168999 256346 109690 180904 172679 157200 78594 201857 52784 147...
output:
-40116549
result:
wrong answer 1st numbers differ - expected: '17137565829', found: '-40116549'