結果

問題 No.9 モンスターのレベル上げ
ユーザー FF256grhyFF256grhy
提出日時 2015-05-12 10:32:26
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 3,191 ms / 5,000 ms
コード長 1,432 bytes
コンパイル時間 294 ms
コンパイル使用メモリ 26,540 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-06 03:47:12
合計ジャッジ時間 4,881 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 65 ms
4,380 KB
testcase_03 AC 57 ms
4,376 KB
testcase_04 AC 31 ms
4,376 KB
testcase_05 AC 22 ms
4,376 KB
testcase_06 AC 11 ms
4,380 KB
testcase_07 AC 3 ms
4,376 KB
testcase_08 AC 13 ms
4,380 KB
testcase_09 AC 62 ms
4,376 KB
testcase_10 AC 2 ms
4,376 KB
testcase_11 AC 42 ms
4,376 KB
testcase_12 AC 28 ms
4,380 KB
testcase_13 AC 3,191 ms
4,380 KB
testcase_14 AC 61 ms
4,376 KB
testcase_15 AC 56 ms
4,380 KB
testcase_16 AC 5 ms
4,380 KB
testcase_17 AC 39 ms
4,380 KB
testcase_18 AC 34 ms
4,376 KB
testcase_19 AC 4 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>

#define N_MAX 1500
#define L_MAX 15000

void make_table();
void add(int, int);

int n, a[N_MAX], b[N_MAX], table[L_MAX + 1], buttle[N_MAX + 1], next[N_MAX + 1];

int main(void) {
	scanf("%d", &n);
	int i, j;
 	for(i = 0; i < n; i++) { scanf("%d", &a[i]); }
	for(i = 0; i < n; i++) { scanf("%d", &b[i]); b[i] /= 2; }
	
	int min = N_MAX + 1;
	for(i = 0; i < n; i++) { // i: 開始位置
		make_table();
		int max = 0, l = 0;
		for(j = 0; j < n; j++) { // (i + j) % n と戦う
			while(table[l] == 0) { l++; }
			int p = table[l];
			buttle[p]++;
			max = max < buttle[p] ? buttle[p] : max;
			table[l] = next[p];
			add(l + b[ (i + j) % n ], p);
		}
		min = max < min ? max : min;
	}
	
	printf("%d\n", min);
	return 0;
}

void make_table() {
	int i;
	for(i = 0; i <= L_MAX; i++) { table[i] = 0; }
	for(i = 0; i <= N_MAX; i++) { buttle[i] = 0; next[i] = 0; }
	for(i = 0; i < n; i++) {
		// buttleはどうせ0なので放置
		next[i + 1] = table[ a[i] ]; // 先頭に挿入していく
		table[ a[i] ] = i + 1; // 0はnullなので+1
	}
	buttle[0] = N_MAX + 1; // 番兵
	return;
}

void add(int l, int p) {
	if(buttle[p] <= buttle[ table[l] ]) { // 先頭に挿入する場合
		next[p] = table[l]; // 前回のはここが間違ってたね
		table[l] = p;
	} else { // 先頭以外
		int q = table[l];
		while( buttle[ next[q] ] < buttle[p] ) { q = next[q]; }
		next[p] = next[q];
		next[q] = p;
	}
	return;
}
0