結果

問題 No.873 バイナリ、ヤバいなり！ｗ
ユーザー Hoi_koroHoi_koro
提出日時 2019-08-30 22:55:36
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 407 ms / 2,000 ms
コード長 2,765 bytes
コンパイル時間 2,498 ms
コンパイル使用メモリ 196,340 KB
実行使用メモリ 326,552 KB
最終ジャッジ日時 2023-09-02 07:10:07
合計ジャッジ時間 6,798 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 175 ms
145,188 KB
testcase_01 AC 92 ms
74,972 KB
testcase_02 AC 391 ms
310,420 KB
testcase_03 AC 307 ms
254,140 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 1 ms
4,380 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 83 ms
65,724 KB
testcase_09 AC 2 ms
4,380 KB
testcase_10 AC 1 ms
4,376 KB
testcase_11 AC 1 ms
4,380 KB
testcase_12 AC 21 ms
19,028 KB
testcase_13 AC 2 ms
4,380 KB
testcase_14 AC 1 ms
4,380 KB
testcase_15 AC 1 ms
4,376 KB
testcase_16 AC 2 ms
4,376 KB
testcase_17 AC 2 ms
4,376 KB
testcase_18 AC 2 ms
4,380 KB
testcase_19 AC 2 ms
4,380 KB
testcase_20 AC 2 ms
4,380 KB
testcase_21 AC 2 ms
4,380 KB
testcase_22 AC 1 ms
4,380 KB
testcase_23 AC 2 ms
4,376 KB
testcase_24 AC 1 ms
4,380 KB
testcase_25 AC 1 ms
4,376 KB
testcase_26 AC 1 ms
4,376 KB
testcase_27 AC 2 ms
4,376 KB
testcase_28 AC 2 ms
4,376 KB
testcase_29 AC 1 ms
4,380 KB
testcase_30 AC 1 ms
4,380 KB
testcase_31 AC 2 ms
4,380 KB
testcase_32 AC 11 ms
10,868 KB
testcase_33 AC 3 ms
4,492 KB
testcase_34 AC 51 ms
41,004 KB
testcase_35 AC 407 ms
326,552 KB
testcase_36 AC 210 ms
168,840 KB
testcase_37 AC 393 ms
326,420 KB
testcase_38 AC 390 ms
326,428 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#if MYDEBUG
#include "lib/cp_debug.hpp"
#else
#define DBG(...) ;
#endif
#if __cplusplus <= 201402L
template <typename T>
T gcd(T a, T b) { return ((a % b == 0) ? b : gcd(b, a % b)); }
template <typename T>
T lcm(T a, T b) { return a / gcd(a, b) * b; }
#endif
using LL = long long;
constexpr LL LINF = 334ll << 53;
constexpr int INF = 15 << 26;
constexpr LL MOD = 1E9 + 7;

namespace Problem {
using namespace std;

class Solver {
 public:
  int n;
  vector<vector<short>> dp;
  vector<deque<int>> lens;
  Solver(LL n) : n(n), dp((int)ceil(sqrt(n)) + 1, vector<short>(n + 1, 30000)){};

  void dfs(int largest, int sum, deque<int> path) {
    DBG(largest, sum, path)
    if (largest == 0 && sum == 0) {
      lens.push_back(path);
      return;
    }
    int d1 = dp[largest - 1][sum];
    int d2 = sum >= largest * largest ? dp[largest][sum - largest * largest] + largest : 30000;
    if (d1 == dp[largest][sum]) {
      dfs(largest - 1, sum, path);
    }
    if (d2 == dp[largest][sum]) {
      path.push_back(largest);
      dfs(largest, sum - largest * largest, path);
    }
  }

  void solve() {
    int m = dp.size() - 1;
    LL ub = 0;
    dp[0][0] = 0;
    for (int i = 1; i <= m; ++i) {
      ub += 3 * i * i;
      for (int j = 0; j <= min<LL>(n, ub); ++j) {
        dp[i][j] = dp[i - 1][j];
        if (j - i * i >= 0) {
          dp[i][j] = min<short>(dp[i][j], dp[i][j - i * i] + i);
        }
      }
    }
    for (int i = 2; i <= m; ++i) {
      for (int j = 0; j <= n; ++j) {
        if (dp[i][j] > dp[i - 1][j]) DBG(i, j)
      }
    }
    dfs(m, n, {});
    DBG(lens)
    vector<string> anss;
    for (auto ans : lens) {
      sort(ans.begin(), ans.end(), [&](int x, int y) -> bool { return (x % 2 > y % 2) || (x % 2 == y % 2 && x < y); });

      vector<int> len;
      while (!ans.empty() && ans.front() % 2 == 1) {
        len.push_back(ans.front());
        ans.pop_front();
      }
      int cnt = 0;
      while (!ans.empty()) {
        if (cnt % 2 == 0) {
          len.push_back(ans.back());
          ans.pop_back();
        } else {
          len.push_back(ans.front());
          ans.pop_front();
        }
        cnt++;
      }
      DBG(len)
      int c = 0;
      string ret = "";
      for (auto z : len) {
        for (int i = 0; i < z; ++i) {
          ret.push_back('0' + c);
          c ^= 1;
        }
        c ^= 1;
      }
      anss.push_back(ret);
    }

    sort(anss.begin(), anss.end());
    cout << anss[0] << endl;
  }
};  // namespace Problem

}  // namespace Problem

int main() {
  std::cin.tie(0);
  std::ios_base::sync_with_stdio(false);
  // std::cout << std::fixed << std::setprecision(12);
  long long n = 0;
  std::cin >> n;

  Problem::Solver sol(n);
  sol.solve();
  return 0;
}
0