結果

問題 No.206 数の積集合を求めるクエリ
ユーザー FF256grhy
提出日時 2015-05-11 02:02:53
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 2,215 ms / 7,000 ms
コード長 1,192 bytes
コンパイル時間 156 ms
コンパイル使用メモリ 24,192 KB
実行使用メモリ 80,512 KB
最終ジャッジ日時 2024-07-05 22:16:51
合計ジャッジ時間 67,747 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:14:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   14 |         scanf("%d%d%d", &l, &m, &n);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
main.cpp:16:39: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   16 |         for(i = 0; i < l; i++) { scanf("%d", &a); bucket_a[a - 1] = 1; }
      |                                  ~~~~~^~~~~~~~~~
main.cpp:17:39: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   17 |         for(i = 0; i < m; i++) { scanf("%d", &b); bucket_b[b - 1] = 1; }
      |                                  ~~~~~^~~~~~~~~~
main.cpp:18:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   18 |         scanf("%d", &q);
      |         ~~~~~^~~~~~~~~~

ソースコード

diff # 

#include <stdio.h>

#define MAX 100000

void make_table();
void count(int, int);

int l, m, n, q;
int bucket_a[MAX], bucket_b[MAX];
int memo[MAX], table[1024][1024][19];

int main(void) {
	int i, j;
	scanf("%d%d%d", &l, &m, &n);
	int a, b;
	for(i = 0; i < l; i++) { scanf("%d", &a); bucket_a[a - 1] = 1; }
	for(i = 0; i < m; i++) { scanf("%d", &b); bucket_b[b - 1] = 1; }
	scanf("%d", &q);
	
	make_table();
	
	for(i = 0; i < MAX / 10; i++) {
	for(j = 0; j <= i;       j++) {
		count(i, j);
	}
	}
	
	for(i = 0; i < q; i++) {
		printf("%d\n", memo[i]);
	}
	return 0;
}

void make_table() {
	int i, j, k, l;
	for(i = 0; i < 1024; i++) {
	for(j = 0; j < 1024; j++) {
		for(k = 0; k < 10; k++) { if( (i >> k) % 2) {
		for(l = 0; l < 10; l++) { if( (j >> l) % 2) {
			table[i][j][ (k - l) + 9 ]++; // k-l : -9 ~ +9 --(+9)--> 0 ~ 18
		} }
		} }
	}
	}
	return;
}

void count(int x, int y) {
	int table_x = 0, table_y = 0;
	int a = 10 * x, b = 10 * y;
	int i;
	for(i = 0; i < 10; i++) {
		table_x += bucket_a[a + i] * (1 << i);
		table_y += bucket_b[b + i] * (1 << i);
	}
	for(i = -9; i <= 9; i++) {
		if(0 <= (a - b) + i) {
			memo[ (a - b) + i ] += table[table_x][table_y][i + 9];
		}
	}
	return;
}
0