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

• 問題: No.206 数の積集合を求めるクエリ
• ユーザー: FF256grhy
• 提出日時: 2015-05-09 14:06:56
• 言語: C++11 (gcc 11.4.0)
• 結果: TLE
• 実行時間: -
• コード長: 1,148 bytes
• コンパイル時間: 197 ms
• コンパイル使用メモリ: 25,716 KB
• 実行使用メモリ: 8,768 KB
• 最終ジャッジ日時: 2023-09-19 09:27:55
• 合計ジャッジ時間: 10,033 ms
• ジャッジサーバーID （参考情報）: judge12 / judge13

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 8,356 KB
testcase_01	AC	2 ms; 4,380 KB
testcase_02	AC	2 ms; 4,380 KB
testcase_03	AC	2 ms; 4,380 KB
testcase_04	AC	1 ms; 4,380 KB
testcase_05	AC	2 ms; 4,380 KB
testcase_06	AC	2 ms; 4,384 KB
testcase_07	AC	2 ms; 4,380 KB
testcase_08	AC	2 ms; 4,380 KB
testcase_09	AC	2 ms; 4,376 KB
testcase_10	AC	2 ms; 4,380 KB
testcase_11	AC	2 ms; 4,380 KB
testcase_12	AC	23 ms; 4,380 KB
testcase_13	AC	14 ms; 4,380 KB
testcase_14	AC	11 ms; 4,380 KB
testcase_15	AC	5 ms; 4,380 KB
testcase_16	AC	18 ms; 4,376 KB
testcase_17	AC	46 ms; 4,380 KB
testcase_18	AC	23 ms; 4,376 KB
testcase_19	AC	41 ms; 4,380 KB
testcase_20	AC	24 ms; 4,380 KB
testcase_21	AC	29 ms; 4,384 KB
testcase_22	AC	29 ms; 4,380 KB
testcase_23	AC	42 ms; 4,380 KB
testcase_24	TLE	-
testcase_25	--	-
testcase_26	--	-
testcase_27	--	-
testcase_28	--	-
testcase_29	--	-
testcase_30	--	-

ソースコード

#include <stdio.h>

//これ実質O(n^2)だし、さすがに通らないやろ…

#define MAX 100000

void marge_sort(int[], int, int);

int l, m, n, a[MAX], b[MAX], q;
int copy[MAX];

int main(void) {
	int i;
	scanf("%d%d%d", &l, &m, &n);
	for(i = 0; i < l; i++) { scanf("%d", &a[i]); }
	for(i = 0; i < m; i++) { scanf("%d", &b[i]); }
	scanf("%d", &q);
	
	marge_sort(a, 0, l - 1);
	marge_sort(b, 0, m - 1);
	
	for(i = 0; i < q; i++) {
		int pa = 0, pb = 0, cnt = 0;
		while(1) {
			if(a[pa] == b[pb] + i) { cnt++; }
			if(a[pa] <= b[pb] + i) { pa++; } else { pb++; }
			if(pa == l || pb == m) { break; }
		}
		printf("%d\n", cnt);
	}
	
	return 0;
}

void marge_sort(int x[], int l, int r) {
	if(l == r) { return; }
	int m = (l + r) / 2;
	marge_sort(x, l, m);
	marge_sort(x, m + 1, r);
	int p = l, q = m + 1, cnt = l;
	while(1) {
		int flag;
		if(m < p && r < q) { break; }
		else if(r < q) { flag = 1; }
		else if(m < p) { flag = 0; }
		else { flag = (x[p] <= x[q]); }
		if(flag) {
			copy[cnt] = x[p];
			p++;
			cnt++;
		} else {
			copy[cnt] = x[q];
			q++;
			cnt++;
		}
	}
	int i;
	for(i = l; i <= r; i++) {
		x[i] = copy[i];
	}
	return;
}