結果

問題 No.873 バイナリ、ヤバいなり！ｗ
コンテスト
ユーザー Hoi_koro
提出日時 2019-08-30 22:55:36
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 378 ms / 2,000 ms
コード長 2,765 bytes
コンパイル時間 2,474 ms
コンパイル使用メモリ 198,528 KB
実行使用メモリ 326,784 KB
最終ジャッジ日時 2024-06-11 14:02:06
合計ジャッジ時間 6,030 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

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