結果

問題 No.206 数の積集合を求めるクエリ
ユーザー rpy3cpprpy3cpp
提出日時 2016-03-27 03:49:48
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 1,411 ms / 7,000 ms
コード長 1,780 bytes
コンパイル時間 414 ms
コンパイル使用メモリ 55,356 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-04-10 02:29:42
合計ジャッジ時間 8,657 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 3 ms
6,940 KB
testcase_07 AC 3 ms
6,944 KB
testcase_08 AC 4 ms
6,940 KB
testcase_09 AC 3 ms
6,940 KB
testcase_10 AC 3 ms
6,940 KB
testcase_11 AC 2 ms
6,940 KB
testcase_12 AC 5 ms
6,940 KB
testcase_13 AC 4 ms
6,944 KB
testcase_14 AC 4 ms
6,944 KB
testcase_15 AC 4 ms
6,944 KB
testcase_16 AC 4 ms
6,940 KB
testcase_17 AC 57 ms
6,940 KB
testcase_18 AC 31 ms
6,944 KB
testcase_19 AC 52 ms
6,944 KB
testcase_20 AC 30 ms
6,940 KB
testcase_21 AC 37 ms
6,940 KB
testcase_22 AC 36 ms
6,944 KB
testcase_23 AC 53 ms
6,940 KB
testcase_24 AC 735 ms
6,940 KB
testcase_25 AC 835 ms
6,940 KB
testcase_26 AC 1,411 ms
6,940 KB
testcase_27 AC 864 ms
6,940 KB
testcase_28 AC 745 ms
6,940 KB
testcase_29 AC 1,274 ms
6,940 KB
testcase_30 AC 721 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
using namespace std;

const int maxN = 100000;

int memo[65536] = { 0 };

bool bA[maxN + 1] = { false };
bool bB[maxN + 1] = { false };

unsigned int A[maxN/32 + 1] = { 0 };
unsigned int B[maxN/32 + 1] = { 0 };

void fill_memo() {
	for (int i = 0; i != (1 << 16); ++i) {
		int cum = 0, j = i;
		while (j) {
			if (j & 1) ++cum;
			j >>= 1;
		}
		memo[i] = cum;
	}
}

void read_data(bool bT[], int L){
	for (int i = 0, val = 0; i != L; ++i) {
		cin >> val;
		bT[val] = true;
	}
}

void fill_array(bool bS[], unsigned int T[], int N);

int count_common(unsigned int A[], unsigned int B[], int N);

inline int bit_count(unsigned int m) {
	return memo[m & 65535] + memo[m >> 16];
}

inline void shift_array(unsigned int B[], int N) {
	for (int i = N / 32; i != 0; --i) {
		B[i] <<= 1;
		if (B[i - 1] >> 31) B[i] |= 1;
	}
	B[0] <<= 1;
}

template <typename Array>
void disp(Array ar[], int N) {
	for (int i = 0; i <= N; ++i) cout << ar[i] << ' ';
	cout << endl;
}

int main()
{
	fill_memo();
	int L, M, N, Q;
	cin >> L >> M >> N;
	read_data(bA, L);
	read_data(bB, M);
//	disp(bA, N);
//	disp(bB, N);
	cin >> Q;
	fill_array(bA, A, N);
	fill_array(bB, B, N);
//	disp(A, N/32 + 1);
//	disp(B, N/32 + 1);
	for (int v = 0; v != Q; ++v) {
		cout << count_common(A, B, N) << '\n';
		shift_array(B, N);
	}
	return 0;
}

void fill_array(bool bS[], unsigned int T[], int N) {
	unsigned int cum = 0, pow2 = 1;
	for (int i = 0; i <= N; ++i) {
		if (bS[i]) cum += pow2;
		pow2 <<= 1;
		if (i % 32 == 31) {
			T[i / 32] = cum;
			cum = 0;
			pow2 = 1;
		}
	}
	if (cum) T[N / 32] = cum;
}

int count_common(unsigned int A[], unsigned int B[], int N) {
	int end = N / 32 + 1;
	int count = 0;
	for (int i = 0; i != end; ++i) {
		count += bit_count(A[i] & B[i]);
	}
	return count;
}
0