結果

問題 No.670 log は定数
コンテスト
ユーザー btk
提出日時 2018-05-26 14:40:25
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
MLE  
実行時間 -
コード長 2,906 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,582 ms
コンパイル使用メモリ 170,192 KB
実行使用メモリ 971,116 KB
最終ジャッジ日時 2024-06-28 18:10:11
合計ジャッジ時間 12,302 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other MLE * 1 -- * 9
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;

#ifdef BTK
#define DEBUG if(1)
#else
#define CIN_ONLY if(1)
struct cww {cww() {CIN_ONLY{ios::sync_with_stdio(false); cin.tie(0);}}
}star;
#define DEBUG if(0)
#endif

#define ALL(v) (v).begin(),(v).end()
#define REC(ret, ...) std::function<ret (__VA_ARGS__)>
template <typename T>inline bool chmin(T &l, T r){bool a = l>r; if (a)l = r; return a;}
template <typename T>inline bool chmax(T &l, T r){bool a = l<r; if (a)l = r; return a;}
template <typename T>istream& operator>>(istream &is, vector<T> &v){for (auto &it : v)is >> it;return is;}

class range {private: struct I { int x; int operator*() { return x; }bool operator!=(I& lhs) { return x<lhs.x; }void operator++() { ++x; } }; I i, n;public:range(int n) :i({ 0 }), n({ n }) {}range(int i, int n) :i({ i }), n({ n }) {}I& begin() { return i; }I& end() { return n; }};
unsigned q[51234567];
int a[212345];
int id[51234567];
namespace Radix {
	using link = int;
	constexpr int BUF = 112345678 ;
	constexpr int END = -1;
	constexpr int RT = 1 << 16;
	struct node {
		int val;
		link next;
	}pool[BUF];

	struct PoolManeger {
		node* const data;
		link ptr;
		PoolManeger(node* const buf = pool):data(buf),ptr(0) {}
		inline link getRange(int size) {
			int base = ptr;
			ptr += size;
			return base;
		}
		inline link get() {
			return ptr++;
		}
		inline void reset() {
			ptr = 0;
		}
	};
	struct low{
		static inline int fix(const int a) {
			return (q[a] << 16) >> 16;
		}
	};
	struct high{
		static inline int fix(const int a) {
			return q[a] >> 16;
		}
	};
	template<typename FIX, typename ITR>
	void sortHalf(const ITR bg, const ITR ed) {
		const int n = distance(bg, ed);
		PoolManeger maneger;

		node* const t = maneger.data;
		link base = maneger.getRange(RT);
		for (int i = 0; i < RT; i++) {
			t[base + i].next = END;
		}
		for (auto it = bg; it != ed; ++it) {
			int fixed = FIX::fix(*it);
			const link id = maneger.get();
			t[id].next = t[fixed].next;
			t[fixed].next = id;
			t[id].val = *it;
		}
		auto ptr = bg;
		for (int i = 0; i < RT; i++) {
			for (link p = t[base + i].next; p != END; p = t[p].next) {
				(*ptr) = t[p].val;
				++ptr;
			}
		}
	}
	template<typename ITR>
	void sort(const ITR bg,const ITR ed) {
		sortHalf<low,ITR>(bg, ed);
		reverse(bg, ed);
		sortHalf<high, ITR>(bg, ed);
	}
}

using ull = unsigned long long;

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

int main() {
	int N, Q;
	cin >> N >> Q >> seed;
	for (int i = 0; i < 10000; i++) next();
	for (int i = 0; i < N; i++) a[i] = next();
	for (int i = 0; i < Q; i++) q[i] = next();
	LL ret = 0;
	sort(a,a+N);
	iota(id, id + Q, 0);
	Radix::sort(id, id + Q);
	LL j = 0;
	for (int i : range(Q)) {
		while (j < N&&a[j] < q[id[i]])j++;
		ret ^= j * id[i];
	}
	cout << ret << endl;
	return 0;
}
0