Submission #71718619

---

Source Code Expand

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <iomanip>

using namespace std;

struct BigInt {
    vector<int> digits;
    static const int BASE = 1000000000;

    BigInt(long long v = 0) {
        if (v == 0) digits.push_back(0);
        while (v > 0) {
            digits.push_back(v % BASE);
            v /= BASE;
        }
    }

    void trim() {
        while (digits.size() > 1 && digits.back() == 0) {
            digits.pop_back();
        }
    }

    bool operator<(const BigInt& other) const {
        if (digits.size() != other.digits.size()) return digits.size() < other.digits.size();
        for (int i = digits.size() - 1; i >= 0; --i) {
            if (digits[i] != other.digits[i]) return digits[i] < other.digits[i];
        }
        return false;
    }
    
    bool operator>=(const BigInt& other) const {
        return !(*this < other);
    }

    BigInt operator+(const BigInt& other) const {
        BigInt res;
        res.digits.clear();
        int carry = 0;
        for (size_t i = 0; i < max(digits.size(), other.digits.size()) || carry; ++i) {
            int sum = carry + (i < digits.size() ? digits[i] : 0) + (i < other.digits.size() ? other.digits[i] : 0);
            res.digits.push_back(sum % BASE);
            carry = sum / BASE;
        }
        return res;
    }

    BigInt operator-(const BigInt& other) const {
        BigInt res;
        res.digits.clear();
        int borrow = 0;
        for (size_t i = 0; i < digits.size(); ++i) {
            int sub = digits[i] - borrow - (i < other.digits.size() ? other.digits[i] : 0);
            if (sub < 0) {
                sub += BASE;
                borrow = 1;
            } else {
                borrow = 0;
            }
            res.digits.push_back(sub);
        }
        res.trim();
        return res;
    }
    
    bool can_subtract(const BigInt& other) const {
        return *this >= other;
    }
};

struct SimState {
    long double apples;
    long double B[4][10];
    int P[4][10];
    int N, L;
    const vector<int>& A;
    
    SimState(int n, int l, const vector<int>& a_ref) : N(n), L(l), A(a_ref) {
        apples = 0;
        for(int i=0; i<L; ++i) {
            for(int j=0; j<N; ++j) {
                B[i][j] = 1.0;
                P[i][j] = 0;
            }
        }
    }

    void step() {
        for(int j=0; j<N; ++j) {
            apples += (long double)A[j] * B[0][j] * P[0][j];
        }
        for(int i=1; i<L; ++i) {
            for(int j=0; j<N; ++j) {
                B[i-1][j] += B[i][j] * P[i][j];
            }
        }
    }
};

int N, L, T;
long long K_init;
vector<int> A;
vector<vector<long long>> C_init;

struct GameState {
    BigInt apples;
    BigInt B[4][10];
    int P[4][10];

    GameState() {
        apples = BigInt(0);
        for(int i=0; i<4; ++i) {
            for(int j=0; j<10; ++j) {
                B[i][j] = BigInt(1);
                P[i][j] = 0;
            }
        }
    }
};

int main() {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);

    cin >> N >> L >> T >> K_init;
    A.resize(N);
    for(int i=0; i<N; ++i) cin >> A[i];
    
    C_init.resize(L, vector<long long>(N));
    for(int i=0; i<L; ++i) {
        for(int j=0; j<N; ++j) {
            cin >> C_init[i][j];
        }
    }

    GameState currentState;
    currentState.apples = BigInt(K_init);

    for (int t = 0; t < T; ++t) {
        int best_action_i = -1;
        int best_action_j = -1;
        long double max_score = -1.0;

        SimState baseSim(N, L, A);
        
        auto to_double = [](const BigInt& b) -> long double {
            long double res = 0;
            long double p = 1;
            for(size_t i=0; i<b.digits.size(); ++i) {
                res += b.digits[i] * p;
                p *= BigInt::BASE;
            }
            return res;
        };

        baseSim.apples = to_double(currentState.apples);
        for(int i=0; i<L; ++i) {
            for(int j=0; j<N; ++j) {
                baseSim.B[i][j] = to_double(currentState.B[i][j]);
                baseSim.P[i][j] = currentState.P[i][j];
            }
        }

        vector<pair<int, int>> candidates;
        candidates.push_back({-1, -1});
        for(int i=0; i<L; ++i) {
            for(int j=0; j<N; ++j) {
                candidates.push_back({i, j});
            }
        }

        for (auto p : candidates) {
            int act_i = p.first;
            int act_j = p.second;
            
            BigInt cost(0);
            if (act_i != -1) {
                long long current_cost_val = C_init[act_i][act_j] * (long long)(currentState.P[act_i][act_j] + 1);
                cost = BigInt(current_cost_val);
                
                if (!currentState.apples.can_subtract(cost)) {
                    continue;
                }
            }

            SimState sim = baseSim;
            
            if (act_i != -1) {
                sim.apples -= (long double)C_init[act_i][act_j] * (sim.P[act_i][act_j] + 1);
                sim.P[act_i][act_j] += 1;
            }

            sim.step();

            for (int k = t + 1; k < T; ++k) {
                sim.step();
            }

            if (sim.apples > max_score) {
                max_score = sim.apples;
                best_action_i = act_i;
                best_action_j = act_j;
            }
        }

        if (best_action_i == -1) {
            cout << -1 << endl;
        } else {
            cout << best_action_i << " " << best_action_j << endl;
            long long cost_val = C_init[best_action_i][best_action_j] * (long long)(currentState.P[best_action_i][best_action_j] + 1);
            currentState.apples = currentState.apples - BigInt(cost_val);
            currentState.P[best_action_i][best_action_j]++;
        }

        BigInt apple_gain(0);
        for(int j=0; j<N; ++j) {
            if (currentState.P[0][j] > 0) {
                long long mul = (long long)A[j] * currentState.P[0][j];
                
                BigInt term = currentState.B[0][j];
                long long carry = 0;
                for (size_t k = 0; k < term.digits.size() || carry; ++k) {
                    if (k == term.digits.size()) term.digits.push_back(0);
                    long long cur = term.digits[k] * mul + carry;
                    term.digits[k] = cur % BigInt::BASE;
                    carry = cur / BigInt::BASE;
                }
                while (carry) {
                    term.digits.push_back(carry % BigInt::BASE);
                    carry /= BigInt::BASE;
                }
                apple_gain = apple_gain + term;
            }
        }
        currentState.apples = currentState.apples + apple_gain;

        for(int i=1; i<L; ++i) {
            for(int j=0; j<N; ++j) {
                if (currentState.P[i][j] > 0) {
                    long long mul = currentState.P[i][j];
                    
                    BigInt add_term = currentState.B[i][j];
                    long long carry = 0;
                    for (size_t k = 0; k < add_term.digits.size() || carry; ++k) {
                        if (k == add_term.digits.size()) add_term.digits.push_back(0);
                        long long cur = add_term.digits[k] * mul + carry;
                        add_term.digits[k] = cur % BigInt::BASE;
                        carry = cur / BigInt::BASE;
                    }
                     while (carry) {
                        add_term.digits.push_back(carry % BigInt::BASE);
                        carry /= BigInt::BASE;
                    }
                    
                    currentState.B[i-1][j] = currentState.B[i-1][j] + add_term;
                }
            }
        }
    }

    return 0;
}

Submission Info

Judge Result