結果

問題 No.206 数の積集合を求めるクエリ
ユーザー rpy3cpprpy3cpp
提出日時 2016-03-27 03:33:40
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 1,746 bytes
コンパイル時間 593 ms
コンパイル使用メモリ 55,308 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-04-10 02:26:41
合計ジャッジ時間 6,914 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 3 ms
6,944 KB
testcase_07 AC 3 ms
6,940 KB
testcase_08 AC 3 ms
6,940 KB
testcase_09 AC 3 ms
6,944 KB
testcase_10 AC 2 ms
6,940 KB
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 AC 31 ms
6,944 KB
testcase_19 AC 51 ms
6,940 KB
testcase_20 WA -
testcase_21 WA -
testcase_22 AC 35 ms
6,940 KB
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
using namespace std;

const int maxN = 100000;

int memo[65536] = { 0 };

bool bA[maxN] = { false };
bool bB[maxN] = { 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] & 32768) 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;
	for (int i = 0; i <= N; ++i) {
		if (bS[i]) cum += 1 << (i % 32);
		if (i % 32 == 31) {
			T[i / 32] = cum;
			cum = 0;
		}
	}
	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