結果

問題 No.9 モンスターのレベル上げ
コンテスト
ユーザー FF256grhy
提出日時 2015-05-12 08:40:31
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
RE  
実行時間 -
コード長 1,261 bytes
コンパイル時間 159 ms
コンパイル使用メモリ 23,936 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-07-05 23:57:29
合計ジャッジ時間 3,317 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other RE * 20
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:9:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
    9 |         scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
main.cpp:11:39: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   11 |         for(i = 0; i < n; i++) { scanf("%d", &a[i]); }
      |                                  ~~~~~^~~~~~~~~~~~~
main.cpp:12:39: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   12 |         for(i = 0; i < n; i++) { scanf("%d", &b[i]); b[i] /= 2; }
      |                                  ~~~~~^~~~~~~~~~~~~
main.cpp: In function ‘void make_table()’:
main.cpp:42:47: warning: iteration 15001 invokes undefined behavior [-Waggressive-loop-optimizations]
   42 |         for(i = 0; i < 20001; i++) { table[i] = 0; }
      |                                      ~~~~~~~~~^~~
main.cpp:42:22: note: within this loop
   42 |         for(i = 0; i < 20001; i++) { table[i] = 0; }
      |                    ~~^~~~~~~
main.cpp:42:47: warning: ‘void* __builtin_memset(void*, int, long unsigned int)’ writing 80004 bytes into a region of size 60004 overflows the destination [-Wstringop-overflow=]
   42 |         for(i = 0; i < 20001; i++) { table[i] = 0; }
      |                                      ~~~~~~~~~^~~
main.cpp:6:26: note: destination object ‘table’ of size 60004
    6 | int n, a[1500], b[1500], table[15001], buttle[1501], next[1501];
      |                          ^~~~~

ソースコード

diff #
raw source code 

#include <stdio.h>

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

int n, a[1500], b[1500], table[15001], buttle[1501], next[1501];

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 = 1501;
	for(i = 0; i < n; i++) { // i: 開始位置
		int max = 0;
		make_table();
		int min_p = 0;
		for(j = 0; j < n; j++) {
			int k = (i + j) % n;
			
			int l = min_p;
			while(table[l] == 0) { l++; }
			min_p = l;
			
			int p = table[l];
			table[l] = next[p];
			
			buttle[p]++;
			max = max < buttle[p] ? buttle[p] : max;
			add(l + b[k], p);
		}
		min = max < min ? max : min;
	}
	
	printf("%d\n", min);
	return 0;
}

void make_table() {
	int i;
	for(i = 0; i < 20001; i++) { table[i] = 0; }
	for(i = 0; i < 1500; i++) { buttle[i] = 0; next[i] = 0; }
	
	for(i = 0; i < n; i++) {
		next[i + 1] = table[ a[i] ]; // 先頭につないでいく
		table[ a[i] ] = i + 1;
	}
	buttle[0] = 1501; // 番兵
	return;
}

void add(int l, int p) {
	if(buttle[p] <= buttle[ table[l] ]) {
		next[p] = next[ 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