結果
問題 | No.873 バイナリ、ヤバいなり!w |
ユーザー |
![]() |
提出日時 | 2019-08-30 22:27:41 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 3,364 bytes |
コンパイル時間 | 1,973 ms |
コンパイル使用メモリ | 190,288 KB |
実行使用メモリ | 10,408 KB |
最終ジャッジ日時 | 2024-06-24 01:38:35 |
合計ジャッジ時間 | 3,743 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 WA * 2 |
コンパイルメッセージ
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/functional:54, from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/x86_64-pc-linux-gnu/bits/stdc++.h:71, from main.cpp:2: In member function 'void std::_Tuple_impl<_Idx, _Head>::_M_assign(std::_Tuple_impl<_Idx, _UHead>&&) [with _UHead = long int; long unsigned int _Idx = 2; _Head = long int]', inlined from 'void std::_Tuple_impl<_Idx, _Head, _Tail ...>::_M_assign(std::_Tuple_impl<_Idx, _UHead, _UTails ...>&&) [with _UHead = long int; _UTails = {long int}; long unsigned int _Idx = 1; _Head = long int; _Tail = {long int}]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/tuple:399:28, inlined from 'void std::_Tuple_impl<_Idx, _Head, _Tail ...>::_M_assign(std::_Tuple_impl<_Idx, _UHead, _UTails ...>&&) [with _UHead = long int; _UTails = {long int, long int}; long unsigned int _Idx = 0; _Head = long int; _Tail = {long int, long int}]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/tuple:399:28, inlined from 'std::tuple< <template-parameter-1-1> >& std::tuple< <template-parameter-1-1> >::operator=(std::__conditional_t<__assignable<_Elements ...>(), std::tuple< <template-parameter-1-1> >&&, std::__nonesuch&&>) [with _Elements = {long int, long int, long int}]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/tuple:914:17, inlined from 'll calc(ll)' at main.cpp:73:45: /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/tuple:538:13: warning: 'num' may be used uninitialized [-Wmaybe-uninitialized] 537 | _M_head(*this) | ~~~~~~~~~~~~~~ 538 | = std::forward<_UHead>(_Tuple_impl<_Idx, _UHead>::_M_head(__in)); | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ main.cpp: In function 'll calc(ll)': main.cpp:60:37: note: 'num' was declared here 60 | ll pre_idx = n, min_len = 5e15, num;
ソースコード
// #define DEBUGGING#include <bits/stdc++.h>using namespace std;#define endl '\n'#define ALL(V) (V).begin(), (V).end()#define ALLR(V) (V).rbegin(), (V).rend()template <typename T> using V = vector<T>;template <typename T> using VV = V<V<T>>;using ll = int64_t;using ull = uint64_t;using PLL = pair<ll, ll>;template <typename T> const T& var_min(const T &t) { return t; }template <typename T> const T& var_max(const T &t) { return t; }template <typename T, typename... Tail> const T& var_min(const T &t, const Tail&... tail) { return min(t, var_min(tail...)); }template <typename T, typename... Tail> const T& var_max(const T &t, const Tail&... tail) { return max(t, var_max(tail...)); }template <typename T, typename... Tail> void chmin(T &t, const Tail&... tail) { t = var_min(t, tail...); }template <typename T, typename... Tail> void chmax(T &t, const Tail&... tail) { t = var_max(t, tail...); }template <typename T> const T& clamp(const T &t, const T &low, const T &high) { return max(low, min(high, t)); }template <typename T> void chclamp(T &t, const T &low, const T &high) { t = clamp(t, low, high); }namespace init__ {struct InitIO {InitIO() {cin.tie(nullptr);ios_base::sync_with_stdio(false);cout << fixed << setprecision(30);}} init_io;}#ifdef DEBUGGING// #include "../debug/debug.cpp"#include "../../debug/debug.cpp"#else#define DEBUG(...) 0#define DEBUG_SEPARATOR_LINE 0#endiftemplate <typename T>T make_v(T init) { return init; }template <typename T, typename... Tail>auto make_v(T init, size_t s, Tail... tail) {#define rec make_v(init, tail...)return V<decltype(rec)>(s, rec);#undef rec}using TLL = tuple<ll, ll, ll>;V<TLL> dp(3e5 + 10, make_tuple(-1, -1, -1));TLL not_yet = TLL(-1, -1, -1);ll calc(ll n) {if(n <= 1) return n;if(dp[n] != not_yet) return get<0>(dp[n]);ll pre_idx = n, min_len = 5e15, num;for(ll i = 1; i * i <= n; i++) {ll pow2 = i * i;ll div = n / (i * i);auto res = calc(n - div * pow2);ll len = div * i + res;DEBUG(make_tuple(n, i, div, res, len));if(len <= min_len) {num = i;pre_idx = n - div * pow2;min_len = i * div + res;}}dp[n] = make_tuple(min_len, pre_idx, num);return min_len;}int main() {ll N;cin >> N;V<ll> nlis;dp[1] = make_tuple(1, 0ll, 1);calc(N);ll idx = N;while(0 < idx) {ll min_len, pre_idx, num;DEBUG(dp[idx]);tie(min_len, pre_idx, num) = dp[idx];ll diff = (idx - pre_idx);for(ll i = 0; i < diff / (num * num); i++) nlis.push_back(num);idx = pre_idx;}DEBUG(nlis);V<ll> odds, evens;for(auto &&ele : nlis) (ele & 1 ? odds : evens).push_back(ele);sort(ALL(odds));sort(ALLR(evens));deque<ll> deq;for(auto &&ele : evens) deq.push_back(ele);string ans;for(auto &&ele : odds) for(ll i = 0; i < ele; i++) ans += '0' + (i & 1);while(deq.size()) {ll ele = deq.front();deq.pop_front();for(ll i = 0; i < ele; i++) ans += '0' + (i & 1);if(deq.empty()) break;ele = deq.back();deq.pop_back();for(ll i = 0; i < ele; i++) ans += '1' - (i & 1);}cout << ans << endl;return 0;}