結果

問題 No.873 バイナリ、ヤバいなり!w
ユーザー kcvlex
提出日時 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;
    

ソースコード

diff #
プレゼンテーションモードにする

// #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
#endif
template <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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0