結果

問題 No.873 バイナリ、ヤバいなり!w
ユーザー 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0