結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 3 ms
6,816 KB
testcase_02 AC 2 ms
6,820 KB
testcase_03 AC 2 ms
6,820 KB
testcase_04 AC 2 ms
6,820 KB
testcase_05 AC 2 ms
6,816 KB
testcase_06 AC 2 ms
6,820 KB
testcase_07 AC 3 ms
6,820 KB
testcase_08 AC 3 ms
6,820 KB
testcase_09 AC 2 ms
6,820 KB
testcase_10 AC 2 ms
6,824 KB
testcase_11 AC 2 ms
6,820 KB
testcase_12 AC 3 ms
6,816 KB
testcase_13 AC 3 ms
6,816 KB
testcase_14 AC 3 ms
6,820 KB
testcase_15 AC 3 ms
6,816 KB
testcase_16 AC 3 ms
6,820 KB
testcase_17 AC 19 ms
6,816 KB
testcase_18 AC 12 ms
6,820 KB
testcase_19 AC 19 ms
6,816 KB
testcase_20 AC 11 ms
6,816 KB
testcase_21 AC 13 ms
6,820 KB
testcase_22 AC 13 ms
6,820 KB
testcase_23 AC 18 ms
6,816 KB
testcase_24 AC 689 ms
6,820 KB
testcase_25 AC 704 ms
6,820 KB
testcase_26 AC 718 ms
6,816 KB
testcase_27 AC 518 ms
6,820 KB
testcase_28 AC 725 ms
6,816 KB
testcase_29 AC 734 ms
6,816 KB
testcase_30 AC 694 ms
6,816 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <ios>
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;
		B[i] |= (B[i - 1] >> 31);
	}
	B[0] <<= 1;
}


int main()
{
	ios::sync_with_stdio(false);
	fill_memo();
	int L, M, N, Q;
	cin >> L >> M >> N;
	read_data(bA, L);
	read_data(bB, M);
	cin >> Q;
	fill_array(bA, A, N);
	fill_array(bB, B, N);
	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