#25833 (C++11) No.206 数の積集合を求めるクエリ

• 問題: No.206 数の積集合を求めるクエリ
• ユーザー: airis
• 提出日時: 2015-05-09 15:14:23
• 言語: C++11 (gcc 11.4.0)
• 結果: WA
• 実行時間: -
• コード長: 1,582 bytes
• コンパイル時間: 546 ms
• コンパイル使用メモリ: 77,300 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-07-05 21:13:30
• 合計ジャッジ時間: 5,378 ms
• ジャッジサーバーID （参考情報）: judge2 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	3 ms; 5,248 KB
testcase_01	AC	3 ms; 5,376 KB
testcase_02	AC	3 ms; 5,376 KB
testcase_03	AC	3 ms; 5,376 KB
testcase_04	AC	3 ms; 5,376 KB
testcase_05	AC	2 ms; 5,376 KB
testcase_06	AC	3 ms; 5,376 KB
testcase_07	AC	3 ms; 5,376 KB
testcase_08	AC	4 ms; 5,376 KB
testcase_09	AC	3 ms; 5,376 KB
testcase_10	AC	3 ms; 5,376 KB
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	AC	53 ms; 5,376 KB
testcase_18	AC	26 ms; 5,376 KB
testcase_19	AC	46 ms; 5,376 KB
testcase_20	AC	27 ms; 5,376 KB
testcase_21	AC	34 ms; 5,376 KB
testcase_22	AC	33 ms; 5,376 KB
testcase_23	AC	48 ms; 5,376 KB
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	WA	-
testcase_28	WA	-
testcase_29	WA	-
testcase_30	WA	-

ソースコード

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <numeric>
#include <bitset>
#define rep(x, to) for (int x = 0; x < (to); x++)
#define REP(x, a, to) for (int x = (a); x < (to); x++)
#define foreach(itr, x) for (typeof((x).begin()) itr = (x).begin(); itr != (x).end(); itr++)

using namespace std;

typedef long long ll;
typedef pair<int, int> PII;
typedef pair<long, long> PLL;

typedef unsigned long long ull;

int L, M, N, Q;
ull A[1605];
ull B[1605];
ull C[1605];
ull x;
int SIZE = sizeof(ull)*8;
int table16[(1<<16) + 5];

void solve() {
#if 0
	rep(i, 2) {
		rep(j, 64) {
			printf("%d", (A[i]&(1<<j)) > 0);
		}
	}
	puts("");
#endif
	rep(i, Q) {
		int ans = 0;
		for (int j = 1600; j >= 0; j--) {
			if (i > 0) {
				B[j] <<= 1LL;
				if (j - 1 >= 0)  {
					B[j] |= (B[j-1] & (1LL<<(SIZE-1)));
				}
			}
			C[j] = A[j] & B[j];
			ans += table16[(C[j] & 0x000000000000ffffLL)];
			ans += table16[(C[j] & 0x00000000ffff0000LL)>>16];
			ans += table16[(C[j] & 0x0000ffff00000000LL)>>32];
			ans += table16[(C[j] & 0xffff000000000000LL)>>48];
			//cout << ans << endl;
		}
		cout << ans << endl;
	}
}

int main() {
	cin >> L >> M >> N;
	rep(i, L) {
		cin>> x; x--;
		A[x/SIZE] |= (1LL << (x % SIZE));
	}
	rep(i, M) {
		cin>> x; x--;
		B[x/SIZE] |= (1LL << (x % SIZE));
	}
	cin >> Q;
	rep(i, 1 << 16) {
		table16[i] = 0;
		rep(j, 16) {
			table16[i] += ((i & (1 << j)) > 0);
		}
	}
	solve();
	return 0;
}