Submission #1157188

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157188		sshs29hanul	Broken Device 2 (JOI22_device2)	C++20	0 / 100	40 ms	2116 KiB

Anna

#include <bits/stdc++.h>
#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:336777216")
using namespace std;
typedef long long ll;
#define all(x) (x).begin(), (x).end()
#define rep(i, a, b) for (auto i = (a); i < (b); i++)
#define each(x, a) for (auto& x: a)

#define debug if constexpr (xdebug) cout << "[DEBUG] "

constexpr bool xdebug = false;
#include "Anna.h"
#include "Bruno.h"

namespace {
    const int M = 140;
    vector<ll> info = {1, 0, 1};
    const int dm[] = {0, 1, 1, 2, 2, 3};
    int rep_cnt;
}

int Declare() {
    rep(i, 3, M + 1) info.push_back(info[i-2] + info[i-3]);
    if(xdebug) {
        ll ans = 0;
        rep(m, M - 8, M + 1) ans += 4 * (info[m-4] + 2 * info[m-5] + 2 * info[m-6] + info[m-7]);
        debug << ans << "\n\n";
    }
    return M;
}

pair<vector<int>, vector<int>> Anna(ll A) {
    debug << "A: " << A << '\n';
    bool indicator = (A > 5e17l);
    if(indicator) A -= 5e17l;
    bool st = (A > 25e16l);
    if(st) A -= 25e16l;
    A += 998244353;
    int m = M, suffix_idx = 0;
    rep_cnt = 0;
    while(true) {
        ll temp = info[m-4-dm[suffix_idx]];
        if(A <= temp) break;
        A -= temp;
        if(suffix_idx == 5) m--, suffix_idx = 0;
        else suffix_idx++;
        if(++rep_cnt == 10000) {int RAISE = 1 / 0;}
    }
    debug << "indicator: " << indicator << ", st: " << st <<
    ", m: " << m << ", suffix_idx: " << suffix_idx << '\n';
    vector<int> X = {indicator, st, st, st}, Y;
    rep(i, 0, m) Y.push_back((i & 1) ^ indicator);
    bool curr = st;

    m -= 4 + dm[suffix_idx];
    rep_cnt = 0;
    while(m) {
        if(A > info[m-2]) {
            A -= info[m-2];
            curr = !curr;
            rep(_, 0, 3) X.push_back(curr);
            m -= 3;
        } else {
            rep(_, 0, 2) X.push_back(curr);
            m -= 2;
        }
        if(++rep_cnt == 10000) {int RAISE = 1 / 0;}
    }
    vector<int> suffix;
    switch(suffix_idx) {
        case 1: {suffix = {curr}; break;}
        case 2: {suffix = {!curr}; break;}
        case 3: {suffix = {!curr, curr}; break;}
        case 4: {suffix = {!curr, !curr}; break;}
        case 5: {suffix = {!curr, !curr, curr}; break;}
        default: {}
    }
    each(item, suffix) X.push_back(item);

    if(xdebug) {
        debug << "X :\n";
        each(item, X) cout << item;
        cout << '\n';
    }
    return {X, Y};
}

Bruno

#include <bits/stdc++.h>
#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:336777216")
using namespace std;
typedef long long ll;
#define all(x) (x).begin(), (x).end()
#define rep(i, a, b) for (auto i = (a); i < (b); i++)
#define each(x, a) for (auto& x: a)

#define debug if constexpr (xdebug) cout << "[DEBUG] "

constexpr bool xdebug = false;
#include "Anna.h"
#include "Bruno.h"

namespace {
    const int M = 140;
    vector<ll> info = {1, 0, 1};
    const int dm[] = {0, 1, 1, 2, 2, 3};
    int rep_cnt;
}

ll Bruno(vector<int> Z) {
    int m = Z.size() >> 1;
    bool indicator = Z[0];
    int curr_diff = indicator ? 1 : -1;
    int ptr = 0;
    bool indicator_found = false;
    bool curr, st;
    int next_diff = 0;
    rep_cnt = 0;
    while(true) {
        next_diff += (Z[ptr] ? 1 : -1);
        if(Z[ptr] == Z[ptr+1]) {
            if(!(Z[ptr] ^ indicator) && !indicator_found) {
                indicator_found = true;
                ptr++;
                continue;
            }
            curr = st = Z[ptr];
            break;
        }
        ptr++;
        if(++rep_cnt == 10000) {int RAISE = 1 / 0;}
    }
    int X_ptr = 1;
    bool Y_ptr = false;
    int prev_ptr = 1;
    vector<bool> X_retrieved;
    int suffix_idx = -1;
    while(true) {
        if(X_ptr + 3 >= m) {
            while(++ptr < Z.size()) next_diff += (Z[ptr] ? 1 : -1);
            if((Y_ptr ^ m) & 1) {
                if(Y_ptr ^ indicator) curr_diff++;
                else curr_diff--;
            }
            int final_crit = curr ? (next_diff - curr_diff) : (curr_diff - next_diff);
            int tail_sz = m - X_ptr;
            final_crit = (tail_sz - final_crit) >> 1;
            debug << tail_sz << ' ' << final_crit << '\n';
            if(tail_sz == 1) {
                suffix_idx = final_crit ? 1 : 2;
            } else if(tail_sz == 2) {
                suffix_idx = final_crit ? 3 : 4;
            } else {
                suffix_idx = final_crit ? 5 : 0;
            }
            if(!suffix_idx) X_retrieved.push_back(true);
            break;
        }
        if(++ptr == Z.size() - 1) {
            next_diff += (Z[ptr] ? 1 : -1);
            if((Y_ptr ^ m) & 1) {
                if(Y_ptr ^ indicator) curr_diff++;
                else curr_diff--;
            }
            int final_crit = curr ? (next_diff - curr_diff) : (curr_diff - next_diff);
            int tail_sz = m - X_ptr;
            final_crit = (tail_sz - final_crit) >> 1;
            if(tail_sz & 1) {
                switch(final_crit) {
                    case 0: {suffix_idx = 0; break;}
                    case 1: {suffix_idx = 3; break;}
                    case 2: {suffix_idx = 4; break;}
                    default: {}
                }
            } else {
                switch(final_crit) {
                    case 0: {suffix_idx = 1; break;}
                    case 1: {suffix_idx = 2; break;}
                    case 2: {suffix_idx = 5; break;}
                    default: {}
                }
            }
            tail_sz -= dm[suffix_idx];
            if(tail_sz) {
                X_retrieved.push_back(true);
                rep(_, 0, (tail_sz - 3) >> 1) X_retrieved.push_back(false);
            }
            break;
        }
        if(Z[ptr] == !curr && Z[ptr+1] == !curr) {
            int crit = curr ? (next_diff - curr_diff) : (curr_diff - next_diff);
            if(prev_ptr != 1) X_retrieved.push_back(true);
            if(!(crit & 1)) {
                if(Y_ptr ^ indicator ^ curr) crit++;
                else crit--;
                Y_ptr = !Y_ptr;
            }
            rep(_, 0, (crit - 3) >> 1) X_retrieved.push_back(false);
            X_ptr += crit;
            curr_diff = next_diff, curr = !curr, prev_ptr = ptr;
        }
        next_diff += (Z[ptr] ? 1 : -1);
    }
    if(xdebug) {
        debug << "indicator: " << indicator << ", st: " << st <<
        ", m: " << m << ", suffix_idx: " << suffix_idx << '\n';
        debug << "X_retrieved :\n";
        cout << indicator << st << st << st;
        bool temp_curr = st;
        rep(i, 0, X_retrieved.size()) {
            if(X_retrieved[i]) {
                temp_curr = !temp_curr;
                cout << temp_curr << temp_curr << temp_curr;
            } else cout << temp_curr << temp_curr;
        }
        switch(suffix_idx) {
            case 1: {cout << temp_curr; break;}
            case 2: {cout << !temp_curr; break;}
            case 3: {cout << !temp_curr << temp_curr; break;}
            case 4: {cout << !temp_curr << !temp_curr; break;}
            case 5: {cout << !temp_curr << !temp_curr << temp_curr; break;}
            default: {}
        }
        cout << '\n';
    }

    ll A = -998244352;
    if(indicator) A += 5e17l;
    if(st) A += 25e16l;
    int temp_m = M, temp_suffix_idx = 0;
    while(temp_m > m || temp_suffix_idx < suffix_idx) {
        ll temp = info[temp_m-4-dm[temp_suffix_idx]];
        A += temp;
        if(temp_suffix_idx == 5) temp_m--, temp_suffix_idx = 0;
        else temp_suffix_idx++;
    }
    m -= 4 + dm[suffix_idx];
    rep(i, 0, X_retrieved.size()) {
        if(X_retrieved[i]) {
            A += info[m-2];
            m -= 3;
        } else m -= 2;
    }
    return A;
}

Compilation message (stderr)

# 1번째 컴파일 단계

Anna.cpp: In function 'std::pair<std::vector<int>, std::vector<int> > Anna(ll)':
Anna.cpp:48:47: warning: division by zero [-Wdiv-by-zero]
   48 |         if(++rep_cnt == 10000) {int RAISE = 1 / 0;}
      |                                             ~~^~~
Anna.cpp:68:47: warning: division by zero [-Wdiv-by-zero]
   68 |         if(++rep_cnt == 10000) {int RAISE = 1 / 0;}
      |                                             ~~^~~

# 2번째 컴파일 단계

Bruno.cpp: In function 'll Bruno(std::vector<int>)':
Bruno.cpp:44:47: warning: division by zero [-Wdiv-by-zero]
   44 |         if(++rep_cnt == 10000) {int RAISE = 1 / 0;}
      |                                             ~~^~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 3
• Subtask 4: 0 / 12
• Subtask 5: 0 / 15
• Subtask 6: 0 / 60