結果

問題 No.873 バイナリ、ヤバいなり！ｗ
ユーザー ganariyaganariya
提出日時 2019-08-30 23:01:23
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,851 bytes
コンパイル時間 1,930 ms
コンパイル使用メモリ 152,184 KB
実行使用メモリ 8,100 KB
最終ジャッジ日時 2024-06-24 01:44:42
合計ジャッジ時間 12,867 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 AC 243 ms
8,064 KB
testcase_06 AC 244 ms
7,888 KB
testcase_07 AC 243 ms
8,064 KB
testcase_08 WA -
testcase_09 AC 244 ms
7,952 KB
testcase_10 AC 241 ms
7,936 KB
testcase_11 AC 249 ms
8,064 KB
testcase_12 AC 246 ms
8,064 KB
testcase_13 AC 247 ms
7,936 KB
testcase_14 AC 241 ms
8,096 KB
testcase_15 AC 243 ms
7,936 KB
testcase_16 AC 244 ms
7,936 KB
testcase_17 AC 245 ms
7,936 KB
testcase_18 AC 243 ms
8,064 KB
testcase_19 AC 240 ms
7,936 KB
testcase_20 AC 240 ms
7,932 KB
testcase_21 AC 242 ms
8,064 KB
testcase_22 AC 239 ms
8,064 KB
testcase_23 AC 238 ms
7,936 KB
testcase_24 AC 239 ms
8,064 KB
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 AC 242 ms
7,936 KB
testcase_34 AC 239 ms
8,064 KB
testcase_35 WA -
testcase_36 AC 239 ms
8,064 KB
testcase_37 WA -
testcase_38 AC 240 ms
8,064 KB
権限があれば一括ダウンロードができます

ソースコード

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;
                } else if (dp[i] == dp[i - dd] + d) {
                    if (d % 2) {
                        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