結果

問題 No.206 数の積集合を求めるクエリ
ユーザー FF256grhyFF256grhy
提出日時 2015-05-11 02:02:53
言語 C++11
(gcc 11.4.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2,030 ms
79,616 KB
testcase_01 AC 2,057 ms
79,616 KB
testcase_02 AC 2,055 ms
79,616 KB
testcase_03 AC 2,036 ms
79,616 KB
testcase_04 AC 2,039 ms
79,616 KB
testcase_05 AC 2,037 ms
79,616 KB
testcase_06 AC 2,013 ms
79,744 KB
testcase_07 AC 2,063 ms
79,616 KB
testcase_08 AC 2,050 ms
79,744 KB
testcase_09 AC 2,042 ms
79,744 KB
testcase_10 AC 2,043 ms
79,616 KB
testcase_11 AC 2,046 ms
79,744 KB
testcase_12 AC 2,040 ms
79,616 KB
testcase_13 AC 2,020 ms
79,744 KB
testcase_14 AC 2,026 ms
79,744 KB
testcase_15 AC 2,004 ms
79,616 KB
testcase_16 AC 1,998 ms
79,744 KB
testcase_17 AC 2,030 ms
80,512 KB
testcase_18 AC 2,187 ms
80,384 KB
testcase_19 AC 2,073 ms
80,512 KB
testcase_20 AC 2,027 ms
80,000 KB
testcase_21 AC 2,021 ms
80,256 KB
testcase_22 AC 2,081 ms
80,256 KB
testcase_23 AC 2,055 ms
80,384 KB
testcase_24 AC 2,039 ms
80,384 KB
testcase_25 AC 2,085 ms
80,256 KB
testcase_26 AC 2,215 ms
80,384 KB
testcase_27 AC 2,112 ms
80,000 KB
testcase_28 AC 2,084 ms
80,128 KB
testcase_29 AC 2,120 ms
80,384 KB
testcase_30 AC 2,069 ms
80,128 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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