結果

問題 No.873 バイナリ、ヤバいなり！ｗ
ユーザー ganariya
提出日時 2019-08-30 22:53:20
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,657 bytes
コンパイル時間 1,693 ms
コンパイル使用メモリ 146,528 KB
最終ジャッジ日時 2025-01-07 16:01:48
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 22 WA * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <unordered_map>
#include <climits>
#include <set>
#include <unordered_set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>
#include <random>
#include <complex>
#include <regex>
#include <locale>
#include <random>
#include <type_traits>

using namespace std;

#define SHOW_VECTOR(v) {std::cerr << #v << "\t:";for(const auto& xxx : v){std::cerr << xxx << " ";}std::cerr << "\n";}
#define SHOW_MAP(v){std::cerr << #v << endl; for(const auto& xxx: v){std::cerr << xxx.first << " " << xxx.second << "\n";}}

using LL = long long;

//------------------------------------------
//------------------------------------------

constexpr LL INF = 1e15;
constexpr LL MAX_N = 300030;

int main() {

    LL N;
    cin >> N;

    vector<pair<LL, LL>> cand;
    for (LL i = 1; i * i <= MAX_N; i++) cand.push_back(make_pair(i, i * i));

    vector<LL> dp(MAX_N + 10, INF);
    vector<LL> prev(MAX_N + 10, INF);
    dp[0] = 0;

    for (LL i = 1; i <= MAX_N; i++) {
        for (int j = 0; j < cand.size(); j++) {
            LL d = cand[j].first;
            LL dd = cand[j].second;
            if (i - dd >= 0) {
                if (dp[i] > dp[i - dd] + d) {
                    dp[i] = dp[i - dd] + d;
                    prev[i] = d;
                }
            }
        }
    }

    LL D = N;
    vector<LL> len;
    while (D != 0) {
        len.push_back(prev[D]);
        D -= prev[D] * prev[D];
    }

    vector<LL> odd, even;
    for (int i = 0; i < len.size(); i++) {
        if (len[i] % 2) odd.push_back(len[i]);
        else even.push_back(len[i]);
    }

    sort(odd.begin(), odd.end());
    sort(even.begin(), even.end());

    string ans = "";
    LL now = 0;

    for (int i = 0; i < odd.size(); i++) {
        LL d = odd[i];
        for (LL j = 0; j < d; j++) {
            ans += ('0' + now);
            if (j != d - 1) {
                now = 1 - now;
            }
        }
    }
    for (int i = 0; i < even.size(); i++) {
        LL d = even[i];
        for (LL j = 0; j < d; j++) {
            ans += ('0' + now);
            if (j != d - 1) {
                now = 1 - now;
            }
        }
    }


    cout << ans << endl;

//    SHOW_VECTOR(dp);
//    SHOW_VECTOR(prev);

}
0