結果

問題 No.9 モンスターのレベル上げ
コンテスト
ユーザー FF256grhy
提出日時 2015-05-12 07:15:50
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 4,337 ms / 5,000 ms
コード長 1,605 bytes
コンパイル時間 279 ms
コンパイル使用メモリ 24,832 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-23 22:38:34
合計ジャッジ時間 21,364 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 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; }
      |                                  ~~~~~^~~~~~~~~~~~~

ソースコード

diff #
raw source code 

#include <stdio.h>

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

int n, a[1500], b[1500], level[1500], buttle[1500];

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; }
	
	marge_sort(a, 0, n - 1);
	
	int min = 1501;
	for(i = 0; i < n; i++) { // i: 開始位置
		for(j = 0; j < n; j++) {
			level [j] = a[j];
			buttle[j] = 0;
		}
		for(j = 0; j < n; j++) {
			level [0] += b[(i + j) % n];
			buttle[0]++;
			int p = 0;
			while(p + 1 < n && win(p, p + 1)) {
				int temp_l = level [p];
				int temp_b = buttle[p];
				level [p] =  level[p + 1];
				buttle[p] = buttle[p + 1];
				level [p + 1] = temp_l;
				buttle[p + 1] = temp_b;
				p++;
			}
		}
		int max = 0;
		for(j = 0; j < n; j++) {
			max = max < buttle[j] ? buttle[j] : max;
		}
		min = max < min ? max : min;
	}
	printf("%d\n", min);
	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 = 0, copy[r - l + 1];
	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++;
		} else {
			copy[cnt] = x[q];
			q++;
		}
		cnt++;
	}
	int i;
	for(i = 0; i < r - l + 1; i++) {
		x[l + i] = copy[i];
	}
	return;
}

int win(int p, int q) { // pの方が大きければ1
	if(level[q]  < level[p]) { return 1; }
	if(level[q] == level[p]) { return buttle[q] < buttle[p]; }
	return 0;
}
0