QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#746903#7937. Fast XORtingMine_KingWA 61ms5648kbC++141.0kb2024-11-14 15:49:522024-11-14 15:49:53

Judging History

你现在查看的是最新测评结果

  • [2024-11-14 15:49:53]
  • 评测
  • 测评结果:WA
  • 用时:61ms
  • 内存:5648kb
  • [2024-11-14 15:49:52]
  • 提交

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'