結果

問題 No.670 log は定数
コンテスト
ユーザー QCFium
提出日時 2020-03-13 21:54:56
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 1,824 bytes
コンパイル時間 2,039 ms
コンパイル使用メモリ 169,740 KB
実行使用メモリ 787,780 KB
最終ジャッジ日時 2024-11-22 20:44:46
合計ジャッジ時間 29,063 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other MLE * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}
void rsort_p(std::pair<int, int> *x, int n) {
	int c[256] = { 0 };
	std::pair<int, int> *r0 = (std::pair<int, int> *) malloc(sizeof(std::pair<int, int>) * n);
	assert(r0);
	for (int i = 0; i < n; i++) c[x[i].first & 0xFF]++;
	for (int i = 1; i < 256; i++) c[i] += c[i - 1];
	for (int i = n - 1; i >= 0; i--) r0[--c[x[i].first & 0xFF]] = x[i];
	memset(c, 0, sizeof(c));
	for (int i = 0; i < n; i++) c[r0[i].first >> 8 & 0xFF]++;
	for (int i = 1; i < 256; i++) c[i] += c[i - 1];
	for (int i = n - 1; i >= 0; i--) x[--c[r0[i].first >> 8 & 0xFF]] = r0[i];
	memset(c, 0, sizeof(c));
	for (int i = 0; i < n; i++) c[x[i].first >> 16 & 0xFF]++;
	for (int i = 1; i < 256; i++) c[i] += c[i - 1];
	for (int i = n - 1; i >= 0; i--) r0[--c[x[i].first >> 16 & 0xFF]] = x[i];
	memset(c, 0, sizeof(c));
	for (int i = 0; i < n; i++) c[r0[i].first >> 24 & 0xFF]++;
	for (int i = 1; i < 256; i++) c[i] += c[i - 1];
	for (int i = n - 1; i >= 0; i--) x[--c[r0[i].first >> 24 & 0xFF]] = r0[i];
	free(r0);
}

uint64_t seed;
int next() {
	 seed = seed ^ (seed << 13);
	 seed = seed ^ (seed >> 7);
	 seed = seed ^ (seed << 17);
	 return (seed >> 33);
}

int main() {
	int n = ri(), q = ri();
	seed = ri();
	for (int i = 0; i < 10000; i++) next();
	
	static std::pair<int, int> a[50200000];
	for (int i = 0; i < n + q; i++) {
		a[i].first = next();
		if (i >= n) a[i].second = i - n;
		else a[i].second = -1;
	}
	n += q;
	rsort_p(a, n);
	int64_t res = 0;
	int cnt = 0;
	for (int i = 0; i < n; ) {
		int j = i + 1;
		while (j < n && a[j].first == a[j - 1].first) j++;
		for (int k = i; k < j; k++) if (a[k].second != -1) res ^= (int64_t) cnt * a[k].second;
		for (int k = i; k < j; k++) if (a[k].second == -1) cnt++;
		i = j;
	}
	printf("%" PRId64 "\n", res);
	return 0;
}
0