#374082 (C++14) No.873 バイナリ、ヤバいなり！ｗ

提出ソース

結果

問題	No.873 バイナリ、ヤバいなり！ｗ
ユーザー	kcvlex
提出日時	2019-08-30 22:27:41
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	WA (最新) AC (最初)
実行時間	-
コード長	3,364 bytes
コンパイル時間	1,930 ms
コンパイル使用メモリ	189,756 KB
実行使用メモリ	10,104 KB
最終ジャッジ日時	2023-09-06 06:59:15
合計ジャッジ時間	4,205 ms
ジャッジサーバーID （参考情報）	judge14 / judge11

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	WA	-
testcase_01	AC	24 ms 10,080 KB
testcase_02	AC	89 ms 9,876 KB
testcase_03	WA	-
testcase_04	AC	3 ms 9,912 KB
testcase_05	AC	4 ms 10,104 KB
testcase_06	AC	4 ms 10,032 KB
testcase_07	AC	4 ms 9,968 KB
testcase_08	AC	21 ms 9,948 KB
testcase_09	AC	4 ms 9,904 KB
testcase_10	AC	4 ms 9,836 KB
testcase_11	AC	4 ms 9,908 KB
testcase_12	AC	7 ms 9,940 KB
testcase_13	AC	4 ms 9,780 KB
testcase_14	AC	4 ms 9,964 KB
testcase_15	AC	4 ms 9,904 KB
testcase_16	AC	4 ms 10,080 KB
testcase_17	AC	5 ms 9,904 KB
testcase_18	AC	5 ms 9,908 KB
testcase_19	AC	4 ms 9,788 KB
testcase_20	AC	3 ms 9,796 KB
testcase_21	AC	4 ms 9,796 KB
testcase_22	AC	4 ms 9,792 KB
testcase_23	AC	5 ms 10,012 KB
testcase_24	AC	4 ms 9,908 KB
testcase_25	AC	4 ms 10,076 KB
testcase_26	AC	5 ms 10,028 KB
testcase_27	AC	4 ms 9,912 KB
testcase_28	AC	4 ms 10,016 KB
testcase_29	AC	4 ms 9,852 KB
testcase_30	AC	4 ms 10,032 KB
testcase_31	AC	4 ms 10,096 KB
testcase_32	AC	6 ms 9,840 KB
testcase_33	AC	4 ms 10,028 KB
testcase_34	AC	14 ms 9,908 KB
testcase_35	AC	92 ms 9,780 KB
testcase_36	AC	48 ms 9,876 KB
testcase_37	AC	94 ms 10,060 KB
testcase_38	AC	94 ms 9,788 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

次のファイルから読み込み:  /usr/local/gcc7/include/c++/12.2.0/functional:54,
         次から読み込み:  /usr/local/gcc7/include/c++/12.2.0/x86_64-pc-linux-gnu/bits/stdc++.h:71,
         次から読み込み:  main.cpp:2:
メンバ関数 ‘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 /usr/local/gcc7/include/c++/12.2.0/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 /usr/local/gcc7/include/c++/12.2.0/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 /usr/local/gcc7/include/c++/12.2.0/tuple:914:17,
    inlined from ‘ll calc(ll)’ at main.cpp:73:45:
/usr/local/gcc7/include/c++/12.2.0/tuple:538:13: 警告: ‘num’ may be used uninitialized [-Wmaybe-uninitialized]
  537 |           _M_head(*this)
      |           ~~~~~~~~~~~~~~
  538 |             = std::forward<_UHead>(_Tuple_impl<_Idx, _UHead>::_M_head(__in));
      |             ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp: 関数 ‘ll calc(ll)’ 内:
main.cpp:60:37: 備考: ‘num’ はここで定義されています
   60 |     ll pre_idx = n, min_len = 5e15, num;
      |                                     ^~~

ソースコード

raw source code

// #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;
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード