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

提出ソース

結果

問題	No.206 数の積集合を求めるクエリ
ユーザー	ふっぴー
提出日時	2017-11-27 23:58:53
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	1,477 ms / 7,000 ms
コード長	3,337 bytes
コンパイル時間	1,567 ms
コンパイル使用メモリ	174,284 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-05-05 13:47:23
合計ジャッジ時間	10,582 ms
ジャッジサーバーID （参考情報）	judge3 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	2 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	3 ms 5,376 KB
testcase_09	AC	4 ms 5,376 KB
testcase_10	AC	3 ms 5,376 KB
testcase_11	AC	2 ms 5,376 KB
testcase_12	AC	8 ms 5,376 KB
testcase_13	AC	7 ms 5,376 KB
testcase_14	AC	7 ms 5,376 KB
testcase_15	AC	7 ms 5,376 KB
testcase_16	AC	8 ms 5,376 KB
testcase_17	AC	73 ms 5,376 KB
testcase_18	AC	39 ms 5,376 KB
testcase_19	AC	66 ms 5,376 KB
testcase_20	AC	38 ms 5,376 KB
testcase_21	AC	46 ms 5,376 KB
testcase_22	AC	46 ms 5,376 KB
testcase_23	AC	68 ms 5,376 KB
testcase_24	AC	874 ms 5,376 KB
testcase_25	AC	947 ms 5,376 KB
testcase_26	AC	1,477 ms 5,376 KB
testcase_27	AC	925 ms 5,376 KB
testcase_28	AC	852 ms 5,376 KB
testcase_29	AC	1,367 ms 5,376 KB
testcase_30	AC	809 ms 5,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include "bits/stdc++.h"
using namespace std;

#define DEBUG(x) cout<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cout<<#v<<":";for(int i=0;i<v.size();i++) cout<<" "<<v[i]; cout<<endl

typedef long long ll;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
const int inf = 1000000001;
const ll INF = 1e18 * 2;
#define MOD 1000000007
#define mod 1000000009
#define pi 3.14159265358979323846
#define Sp(p) cout<<setprecision(15)<< fixed<<p<<endl;
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };

void print_bit(ll n, ll k) {
	ll m = (1LL << (k - 1));
	while (m >= 1) {
		if ((n&m)) {
			cout << 1;
		}
		else {
			cout << 0;
		}
		m >>= 1;
	}
	return;
}


int main() {
	int l, m, n, i0;
	cin >> l >> m >> n;
	vi a(l), b(m);
	for (i0 = 0; i0 < l; i0++) {
		cin >> a[i0];
	}
	for (i0 = 0; i0 < m; i0++) {
		cin >> b[i0];
	}
	sort(a.begin(), a.end());
	sort(b.begin(), b.end());
	//DEBUG_VEC(a);
	//DEBUG_VEC(b);
	vl x(n / 32 + 2), y(n / 32 + 2);
	int ai = 0, bi = 0;
	for (int i = 0;; i++) {
		if (i * 32 > n) {
			break;
		}
		for (int j = 0; j < 32; j++) {
			int z = i * 32 + j;
			if (ai < l) {
				if (a[ai] == z) {
					x[i] |= (1LL << j);
				}
				if (a[ai] <= z) {
					ai++;
				}
			}
			if (bi < m) {
				if (b[bi] == z) {
					y[i] |= (1LL << j);
				}
				if (b[bi] <= z) {
					bi++;
				}
			}
		}
	}
	//DEBUG_VEC(x);
	//DEBUG_VEC(y);

	vi bitstand(1 << 16);
	for (i0 = 0; i0 < (1 << 16); i0++) {
		int cnt = 0;
		int temp = 1;
		for (int i = 0; i < 16; i++) {
			if (i0 & temp) {
				cnt++;
			}
			temp <<= 1;
		}
		bitstand[i0] = cnt;
	}

	int q;
	cin >> q;
	int length = x.size();
	for (i0 = 0; i0 < q; i0++) {
		int i, j;
		for (i = length - 1; i >= 0; i--) {
			//print_bit(y[i], 64);
		}
		//cout << endl;
		int ans = 0;
		for (i = 0; i < length; i++) {
			ll temp = x[i] & y[i];
			ll mask = (1 << 16) - 1;
			for (j = 0; j < 2; j++) {
				ll bit = temp & mask;
				ans += bitstand[bit];
				temp >>= 16;
			}
		}
		ll mask = 1 << 31;
		for (i = length - 1; i >= 0; i--) {
			y[i] = (y[i] & (mask - 1)) << 1;
			if (i != 0) {
				if (y[i - 1] & mask) {
					y[i] |= 1ULL;
				}
			}
		}
		cout << ans << endl;
	}
}

/*
100 100 100 
52 21 91 38 1 8 3 20 17 73 14 82 26 88 25 89 72 56 11 55 9 62 51 32 66 97 58 75 61 74 4 84 86 100 64 87 69 78 54 45 34 7 81 60 98 23 2 16 18 6 5 41 63 57 96 36 99 27 53 30 39 10 42 12 35 92 28 33 50 83 90 22 71 93 15 13 77 70 46 80 67 29 95 24 37 47 68 59 19 44 79 40 65 48 43 85 31 94 76 49 
53 89 78 21 97 44 40 43 86 26 95 82 57 60 66 42 75 45 4 77 91 9 7 90 2 58 51 12 16 27 13 71 52 30 50 8 84 83 65 5 54 85 55 99 6 24 14 47 28 11 76 64 56 1 34 29 3 48 17 33 87 15 94 46 62 70 35 41 68 18 32 96 100 23 25 88 49 73 31 37 59 69 22 98 20 19 92 38 80 79 81 39 67 74 36 63 72 93 61 10 
1

50 50 150 
92 135 12 87 104 130 21 38 60 81 80 145 29 120 52 136 66 57 133 22 1 15 56 111 93 137 114 116 97 115 37 28 32 122 17 113 73 101 100 98 138 127 109 144 91 36 74 134 72 88 
11 25 60 56 75 39 38 8 12 90 9 63 2 58 80 94 28 45 31 34 100 13 88 35 85 3 54 43 40 71 19 21 69 98 66 73 65 46 52 84 77 17 59 67 4 99 7 51 62 83 
150
*/

yukicoder

結果

テストケース

ソースコード