#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,973 ms
コンパイル使用メモリ	190,288 KB
実行使用メモリ	10,408 KB
最終ジャッジ日時	2024-06-24 01:38:35
合計ジャッジ時間	3,743 ms
ジャッジサーバーID （参考情報）	judge5 / judge4

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	WA	-
testcase_01	AC	22 ms 10,300 KB
testcase_02	AC	84 ms 10,220 KB
testcase_03	WA	-
testcase_04	AC	4 ms 10,264 KB
testcase_05	AC	4 ms 10,208 KB
testcase_06	AC	4 ms 10,232 KB
testcase_07	AC	5 ms 10,212 KB
testcase_08	AC	21 ms 10,292 KB
testcase_09	AC	4 ms 10,140 KB
testcase_10	AC	5 ms 10,308 KB
testcase_11	AC	5 ms 10,320 KB
testcase_12	AC	8 ms 10,260 KB
testcase_13	AC	5 ms 10,220 KB
testcase_14	AC	4 ms 10,296 KB
testcase_15	AC	5 ms 10,236 KB
testcase_16	AC	5 ms 10,224 KB
testcase_17	AC	5 ms 10,248 KB
testcase_18	AC	4 ms 10,316 KB
testcase_19	AC	5 ms 10,296 KB
testcase_20	AC	4 ms 10,288 KB
testcase_21	AC	4 ms 10,168 KB
testcase_22	AC	4 ms 10,248 KB
testcase_23	AC	4 ms 10,260 KB
testcase_24	AC	5 ms 10,224 KB
testcase_25	AC	4 ms 10,348 KB
testcase_26	AC	4 ms 10,304 KB
testcase_27	AC	5 ms 10,252 KB
testcase_28	AC	4 ms 10,292 KB
testcase_29	AC	5 ms 10,264 KB
testcase_30	AC	4 ms 10,208 KB
testcase_31	AC	5 ms 10,248 KB
testcase_32	AC	6 ms 10,312 KB
testcase_33	AC	5 ms 10,220 KB
testcase_34	AC	14 ms 10,408 KB
testcase_35	AC	89 ms 10,288 KB
testcase_36	AC	47 ms 10,344 KB
testcase_37	AC	90 ms 10,328 KB
testcase_38	AC	88 ms 10,232 KB

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

コンパイルメッセージ

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;

ソースコード

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

結果

テストケース

コンパイルメッセージ

ソースコード