結果
問題 | No.873 バイナリ、ヤバいなり!w |
ユーザー |
![]() |
提出日時 | 2019-08-30 22:52:53 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 84 ms / 2,000 ms |
コード長 | 1,544 bytes |
コンパイル時間 | 770 ms |
コンパイル使用メモリ | 105,080 KB |
実行使用メモリ | 5,888 KB |
最終ジャッジ日時 | 2024-06-11 14:01:47 |
合計ジャッジ時間 | 2,363 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
// includes {{{#include<iostream>#include<iomanip>#include<algorithm>#include<vector>#include<stack>#include<queue>#include<map>#include<set>#include<tuple>#include<cmath>#include<random>#include<cassert>#include<bitset>#include<cstdlib>// #include<deque>// #include<multiset>// #include<cstring>// #include<bits/stdc++.h>// }}}using namespace std;using ll = long long;constexpr ll inf = 1e18;ll dp[312345];template <class T, class U> inline void smax(T &a, U b) { a = a > b ? a : b; }template <class T, class U> inline void smin(T &a, U b) { a = a < b ? a : b; }int main() {std::ios::sync_with_stdio(false), std::cin.tie(0);ll n;cin >> n;for(int i = 1; i <= n; i++) dp[i] = inf;for(int i = 1; i * i <= n; i++) {for(int j = 0; j + i * i <= n; j++) {smin(dp[j+i*i], dp[j] + i);}}auto usable = [](ll n, ll x) -> bool {return n >= x * x and dp[n] == x + dp[n - x * x];};string ans;int last = 0;auto add = [&](ll x) -> void {for(int i = 0; i < x; i++) ans += '0' + last, last ^= 1;last ^= 1;};for(int i = 1; i*i <= n; i+=2) {while(usable(n, i)) {n -= i*i;add(i);}}ll l = 2;ll r = n/2*2;while(n) {if(last) {// 短くwhile(!usable(n, l)) l+=2;assert(n >= l * l);n -= l*l;add(l);} else {// 長くwhile(!usable(n, r)) r-=2;assert(n >= r * r);assert(r >= 2);n -= r*r;add(r);}}cout << ans << endl;return 0;}