Submission #70292550

---

Source Code Expand

#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <random>
#include <chrono>
#include <algorithm>
#include <functional>
#include <cmath> 
using namespace std;

const int N = 200;

int H[N];
int C[N];
int A[N][N];
double tradeoff_score[N];

auto start_time = chrono::high_resolution_clock::now();
double get_time_elapsed() {
    auto now = chrono::high_resolution_clock::now();
    return chrono::duration<double>(now - start_time).count();
}
const double TIME_LIMIT = 1.95;

mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());

struct GameState {
    vector<int> current_H;
    vector<int> current_C;
    vector<bool> is_open;
    int unopened_boxes;

    GameState() {
        current_H.resize(N);
        current_C.resize(N);
        is_open.resize(N, false);
        unopened_boxes = N;
        for (int i = 0; i < N; ++i) {
            current_H[i] = H[i];
            current_C[i] = C[i];
        }
    }
    
    GameState(const GameState& other) = default;

    bool execute_attack(int weapon, int box) {
        if (box < 0 || box >= N || is_open[box]) return false;
        
        int damage = 0;
        if (weapon == -1) {
            damage = 1;
        } else {
            if (weapon < 0 || weapon >= N || !is_open[weapon] || current_C[weapon] == 0) return false;
            damage = A[weapon][box];
            current_C[weapon]--;
        }

        current_H[box] -= damage;
        if (current_H[box] <= 0) {
            is_open[box] = true;
            unopened_boxes--;
        }
        return true;
    }
};

pair<int, int> find_best_attack(GameState& state, double time_ratio) {
    int best_w = -1;
    int best_b = -1;
    double max_score = -1.0;

    vector<int> available_weapons = {-1};
    for (int i = 0; i < N; ++i) {
        if (state.is_open[i] && state.current_C[i] > 0) {
            available_weapons.push_back(i);
        }
    }

    vector<int> unopened_boxes;
    for (int i = 0; i < N; ++i) {
        if (!state.is_open[i]) {
            unopened_boxes.push_back(i);
        }
    }
    
    if (unopened_boxes.empty()) {
        return {-1, -1};
    }

    const int sample_size = (time_ratio < 0.5) ? 15 : 25;
    const int WEAPON_SAMPLES = sample_size;
    const int BOX_SAMPLES = sample_size;

    for (int i = 0; i < WEAPON_SAMPLES; ++i) {
        int w = available_weapons[gen() % available_weapons.size()];
        for (int j = 0; j < BOX_SAMPLES; ++j) {
            int b = unopened_boxes[gen() % unopened_boxes.size()];

            int damage = (w == -1) ? 1 : A[w][b];
            int effectiveness = min(damage, state.current_H[b]);
            
            double score = (double)effectiveness;
            
            if (damage >= state.current_H[b]) {
                score += 1000000.0;
                score += tradeoff_score[b] * 1000.0;
            }

            if (score > max_score) {
                max_score = score;
                best_w = w;
                best_b = b;
            }
        }
    }

    if (best_w == -1) {
        best_w = -1;
        best_b = unopened_boxes[0];
    }

    return {best_w, best_b};
}

vector<pair<int, int>> complete_solution_from_state(GameState state, double time_ratio) {
    vector<pair<int, int>> attacks;
    const int MAX_ATTACKS = N * 500;
    int attack_count = 0;

    while (state.unopened_boxes > 0 && attack_count < MAX_ATTACKS) {
        pair<int, int> move = find_best_attack(state, time_ratio);
        if (move.first == -1 && move.second == -1) break;
        
        state.execute_attack(move.first, move.second);
        attacks.push_back(move);
        attack_count++;
    }
    
    if (state.unopened_boxes > 0) {
        return {};
    }
    return attacks;
}

vector<pair<int, int>> generate_initial_solution() {
    GameState state;
    vector<pair<int, int>> attacks;
    
    vector<int> box_indices(N);
    iota(box_indices.begin(), box_indices.end(), 0);
    
    sort(box_indices.begin(), box_indices.end(), [&](int a, int b) {
        return tradeoff_score[a] > tradeoff_score[b];
    });

    const int K_INVESTMENT = 4;
    for (int i = 0; i < K_INVESTMENT; ++i) {
        int box_to_open = box_indices[i];
        if (state.is_open[box_to_open]) continue;
        
        for(int j = 0; j < H[box_to_open]; ++j) {
            state.execute_attack(-1, box_to_open);
            attacks.push_back({-1, box_to_open});
        }
    }

    vector<pair<int, int>> phase_2_attacks = complete_solution_from_state(state, 0.0);
    
    attacks.insert(attacks.end(), phase_2_attacks.begin(), phase_2_attacks.end());
    
    return attacks;
}

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

    start_time = chrono::high_resolution_clock::now();

    int N_in; cin >> N_in;
    for (int i = 0; i < N; ++i) cin >> H[i];
    for (int i = 0; i < N; ++i) cin >> C[i];
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            cin >> A[i][j];
        }
    }

    for (int i = 0; i < N; ++i) {
        long long total_damage = 0;
        for (int j = 0; j < N; ++j) {
            total_damage += A[i][j];
        }
        double value = (double)C[i] * total_damage;
        double cost = H[i];
        
        tradeoff_score[i] = (cost == 0) ? 0 : value / cost;
    }

    vector<pair<int, int>> best_solution = generate_initial_solution();
    int best_score = best_solution.size();
    if (best_solution.empty()) {
        return 1;
    }

    double START_TEMP = 20.0;
    double END_TEMP = 0.1;

    while (true) {
        double time_elapsed = get_time_elapsed();
        if (time_elapsed >= TIME_LIMIT) {
            break;
        }
        
        double time_ratio = time_elapsed / TIME_LIMIT;
        
        int destroy_point = gen() % best_solution.size();

        GameState state;
        vector<pair<int, int>> new_solution;
        bool replay_ok = true;
        for (int i = 0; i < destroy_point; ++i) {
            if (!state.execute_attack(best_solution[i].first, best_solution[i].second)) {
                replay_ok = false;
                break;
            }
            new_solution.push_back(best_solution[i]);
        }
        if (!replay_ok) continue;

        // Pass the time_ratio to the repair function
        vector<pair<int, int>> repair_attacks = complete_solution_from_state(state, time_ratio);
        
        if (repair_attacks.empty()) {
            continue;
        }

        new_solution.insert(new_solution.end(), repair_attacks.begin(), repair_attacks.end());
        int new_score = new_solution.size();
        
        double temperature = START_TEMP + (END_TEMP - START_TEMP) * time_ratio;

        if (new_score < best_score) {
            best_score = new_score;
            best_solution = new_solution;
        }
        else {
            double delta = (double)(new_score - best_score);
            double acceptance_prob = exp(-delta / temperature);
            
            if ((gen() / (double)mt19937::max()) < acceptance_prob) {
                best_score = new_score;
                best_solution = new_solution;
            }
        }
    }

    for (const auto& move : best_solution) {
        cout << move.first << " " << move.second << "\n";
    }

    return 0;
}

Submission Info

Judge Result