結果

問題 No.9 モンスターのレベル上げ
コンテスト
ユーザー らっしー(raccy)
提出日時 2015-01-27 23:16:06
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 174 ms / 5,000 ms
コード長 1,937 bytes
コンパイル時間 626 ms
コンパイル使用メモリ 59,080 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-23 22:17:43
合計ジャッジ時間 2,870 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

/*
やっていることは10107のRubyと一緒なのに、実行速度が違いすぎて泣きたい。
*/
#include <iostream>
#include <utility>
#include <algorithm>
#include <cstring>

const int MAX_N = 1500;

int main() {
  int n, i, j, k, pos, target;
  int n1;
  int org_mon_list[MAX_N + 2];
  int mon_list[MAX_N + 2];
  int exp_list[MAX_N];
  int low_count = MAX_N;
  int max_count;

  std::cin >> n;
  n1 = n + 1;

  org_mon_list[0] = 0;
  for (i = 0; i < n; ++i) {
    std::cin >> j;
    pos = i + 1;
    org_mon_list[pos] = j * n1;
    while (pos > 1) {
      if (org_mon_list[pos] < org_mon_list[pos / 2]) {
        std::swap(org_mon_list[pos], org_mon_list[pos / 2]);
        pos = pos / 2;
      } else {
        break;
      }
    }
  }
  org_mon_list[n + 1] = 15001 * n1;

  for (i = 0; i < n; ++i) {
    std::cin >> j;
    exp_list[i] = j / 2;
  }

  for (i = 0; i < n; ++i) {
    std::memcpy(mon_list, org_mon_list, sizeof(int) * (n + 2));
    max_count = 0;
    for (j = 0; j < n; ++j) {
      target = mon_list[1] + (exp_list[(i + j) % n] * n1) + 1;
      max_count = std::max(max_count, target % n1);
      k = 1;
      mon_list[1] = target;
      while (k * 2 <= n) {
        if (mon_list[k * 2] < target) {
          if (mon_list[k * 2 + 1] < target) {
            if (mon_list[k * 2] < mon_list[k * 2 + 1]) {
              std::swap(mon_list[k], mon_list[k * 2]);
              k = k * 2;
            } else {
              std::swap(mon_list[k], mon_list[k * 2 + 1]);
              k = k * 2 + 1;
            }
          } else {
            std::swap(mon_list[k], mon_list[k * 2]);
            k = k * 2;
          }
        } else if (mon_list[k * 2 + 1] < target) {
          std::swap(mon_list[k], mon_list[k * 2 + 1]);
          k = k * 2 + 1;
        } else {
          break;
        }
      }
    }
    low_count = std::min(low_count, max_count);
  }
  std::cout << low_count << std::endl;
  return 0;
}
0