結果
問題 | No.873 バイナリ、ヤバいなり!w |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#include <bits/stdc++.h>#if MYDEBUG#include "lib/cp_debug.hpp"#else#define DBG(...) ;#endif#if __cplusplus <= 201402Ltemplate <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; }#endifusing 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 Problemint 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;}