Submission #65951220

---

Source Code Expand

// Your code here
#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <chrono> // For Timer and random seed

// Timer for managing time limits
class Timer {
public:
    Timer() : start_time_(std::chrono::high_resolution_clock::now()) {}

    void reset() {
        start_time_ = std::chrono::high_resolution_clock::now();
    }

    double get_elapsed_seconds() const {
        auto now = std::chrono::high_resolution_clock::now();
        return std::chrono::duration<double>(now - start_time_).count();
    }

private:
    std::chrono::time_point<std::chrono::high_resolution_clock> start_time_;
};


// Parameters (fixed for the problem)
const int M_STATES_FIXED = 12; 
const int MAX_S_LEN_FIXED = 12; 

// Structure to hold problem input
struct ProblemInput {
    std::vector<std::string> S;
    std::vector<int> P;
    int N, M; 
    double L;     

    void read() {
        std::cin >> N >> M >> L; 
        S.resize(N);
        P.resize(N);
        for (int i = 0; i < N; ++i) {
            std::cin >> S[i] >> P[i];
        }
    }
};

// Solution structure
struct Solution {
    std::vector<char> C; 
    std::vector<std::vector<int>> A;

    Solution() { 
        C.resize(M_STATES_FIXED);
        A.resize(M_STATES_FIXED, std::vector<int>(M_STATES_FIXED));
    }
    Solution(int M_states) { 
        C.resize(M_states);
        A.resize(M_states, std::vector<int>(M_states));
    }

    void print() const {
        std::cout << std::fixed << std::setprecision(0); 
        for (size_t i = 0; i < C.size(); ++i) {
            std::cout << C[i];
            for (size_t j = 0; j < A[i].size(); ++j) {
                std::cout << " " << A[i][j];
            }
            std::cout << std::endl;
        }
    }
};

// Score evaluation
class ScoreCalculator {
public:
    const ProblemInput& input;
    std::vector<double> stationary_dist_1; 
    std::vector<double> stationary_dist_2; // For ping-pong buffer
    std::vector<std::vector<double>> A_double; 
    std::vector<std::vector<double>> p_sk_dp; 

    ScoreCalculator(const ProblemInput& prob_input) : input(prob_input) {
        stationary_dist_1.resize(input.M);
        stationary_dist_2.resize(input.M);
        A_double.resize(input.M, std::vector<double>(input.M));
        p_sk_dp.resize(MAX_S_LEN_FIXED, std::vector<double>(input.M));
    }

    double calculate_score(const Solution& sol) {
        for (int i = 0; i < input.M; ++i) {
            for (int j = 0; j < input.M; ++j) {
                A_double[i][j] = sol.A[i][j] / 100.0;
            }
        }
        
        std::vector<double>* pi_current_ptr = &stationary_dist_1;
        std::vector<double>* pi_next_ptr = &stationary_dist_2;

        std::fill(pi_current_ptr->begin(), pi_current_ptr->end(), 0.0);
        if (input.M > 0) {
             (*pi_current_ptr)[0] = 1.0; 
        } else { 
            return 0.0; 
        }
        
        const int POWER_ITERATIONS = 100; 
        for (int iter = 0; iter < POWER_ITERATIONS; ++iter) { 
            std::fill(pi_next_ptr->begin(), pi_next_ptr->end(), 0.0);
            for (int j = 0; j < input.M; ++j) { 
                double val_for_pi_j_next = 0.0;
                for (int i = 0; i < input.M; ++i) { 
                    val_for_pi_j_next += (*pi_current_ptr)[i] * A_double[i][j];
                }
                (*pi_next_ptr)[j] = val_for_pi_j_next;
            }
            std::swap(pi_current_ptr, pi_next_ptr);
        }

        double total_expected_preference = 0;

        for (int k = 0; k < input.N; ++k) { 
            const std::string& Sk = input.S[k];
            int Sk_len = Sk.length();
            if (Sk_len == 0) continue;

            for (int u = 0; u < input.M; ++u) {
                if (sol.C[u] == Sk[0]) {
                    p_sk_dp[0][u] = (*pi_current_ptr)[u];
                } else {
                    p_sk_dp[0][u] = 0.0;
                }
            }

            for (int char_idx = 0; char_idx < Sk_len - 1; ++char_idx) {
                for (int v_next_state = 0; v_next_state < input.M; ++v_next_state) {
                    p_sk_dp[char_idx+1][v_next_state] = 0.0; 
                    if (sol.C[v_next_state] == Sk[char_idx+1]) {
                        double sum_prev_paths = 0;
                        for (int u_curr_state = 0; u_curr_state < input.M; ++u_curr_state) {
                            sum_prev_paths += p_sk_dp[char_idx][u_curr_state] * A_double[u_curr_state][v_next_state];
                        }
                        p_sk_dp[char_idx+1][v_next_state] = sum_prev_paths;
                    }
                }
            }

            double prob_Sk_starts = 0;
            for (int u = 0; u < input.M; ++u) {
                prob_Sk_starts += p_sk_dp[Sk_len-1][u];
            }

            double lambda_k = input.L * prob_Sk_starts;
            double Q_k;
            
            if (prob_Sk_starts < 1e-100 || lambda_k < 1e-9) { 
                 Q_k = lambda_k; 
            } else if (lambda_k > 30) { 
                 Q_k = 1.0;
            } else {
                 Q_k = -std::expm1(-lambda_k); 
            }
            
            if (std::isnan(Q_k) || Q_k < 0) Q_k = 0; 
            if (Q_k > 1.0) Q_k = 1.0;

            total_expected_preference += input.P[k] * Q_k;
        }
        return total_expected_preference;
    }
};

struct Random {
    unsigned int x, y, z, w;
    Random(unsigned int seed) : x(seed), y(362436069), z(521288629), w(88675123) {
        if (seed == 0) x = 123456789; 
    }
    unsigned int next_int() {
        unsigned int t = x ^ (x << 11);
        x = y; y = z; z = w;
        w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
        return w;
    }
    double next_double() { // [0,1)
        return static_cast<double>(next_int()) / 4294967296.0; // 2^32
    }
    int next_int_range(int min_val, int max_val) { // [min_val, max_val]
        if (min_val > max_val) return min_val; 
        return min_val + next_int() % (max_val - min_val + 1);
    }
};

void solve(const ProblemInput& input, Solution& best_sol, double& best_score, Random& rnd, const Timer& overall_timer, double time_limit) {
    
    Solution current_sol(input.M);
    ScoreCalculator score_calc(input);
    double current_score_val = 0.0; // FIX: Declare current_score_val

    if (input.M > 0) {
        int states_per_char_bucket = std::max(1, input.M / 6);
        for (int i = 0; i < input.M; ++i) {
             current_sol.C[i] = 'a' + ((i / states_per_char_bucket) % 6) ; 
        }
    }
    
    std::vector<std::vector<double>> W(input.M, std::vector<double>(input.M, 0.0));
    if (input.M > 0) { 
        for (int u = 0; u < input.M; ++u) {
            for (int v = 0; v < input.M; ++v) {
                double sum_score_weights = 1e-9; 
                for (int k_idx = 0; k_idx < input.N; ++k_idx) {
                    const auto& Sk = input.S[k_idx];
                    for (size_t char_j = 0; char_j < Sk.length() - 1; ++char_j) {
                        if (current_sol.C[u] == Sk[char_j] && current_sol.C[v] == Sk[char_j+1]) {
                            sum_score_weights += input.P[k_idx]; 
                        }
                    }
                }
                W[u][v] = sum_score_weights;
            }
        }
    }


    for (int i = 0; i < input.M; ++i) {
        double row_sum_W = 0;
        for (int j = 0; j < input.M; ++j) {
            row_sum_W += W[i][j];
        }

        if (input.M == 0) continue; 
        if (row_sum_W < 1e-8) { 
            int base_prob = 100 / input.M;
            int remainder = 100 % input.M;
            for (int j = 0; j < input.M; ++j) current_sol.A[i][j] = base_prob;
            for (int j = 0; j < remainder; ++j) current_sol.A[i][j]++;
        } else {
            int current_row_sum_A = 0;
            for (int j = 0; j < input.M; ++j) {
                current_sol.A[i][j] = static_cast<int>(std::round(100.0 * W[i][j] / row_sum_W));
                current_row_sum_A += current_sol.A[i][j];
            }
            
            int diff = 100 - current_row_sum_A;
            
            std::vector<std::pair<double, int>> candidates_W_for_adjust;
            for(int j=0; j<input.M; ++j) candidates_W_for_adjust.push_back({W[i][j], j}); 

            if (diff > 0) std::sort(candidates_W_for_adjust.rbegin(), candidates_W_for_adjust.rend()); 
            else std::sort(candidates_W_for_adjust.begin(), candidates_W_for_adjust.end()); 
            
            int initial_abs_diff = std::abs(diff);
            for (int k_iter = 0; k_iter < initial_abs_diff; ++k_iter) {
                if (diff == 0) break;
                int target_j = candidates_W_for_adjust[k_iter % input.M].second; 
                if (diff > 0) {
                    if (current_sol.A[i][target_j] < 100) { current_sol.A[i][target_j]++; diff--; }
                } else { 
                    if (current_sol.A[i][target_j] > 0) { current_sol.A[i][target_j]--; diff++; }
                }
            }
            
            current_row_sum_A = 0; for(int val_A : current_sol.A[i]) current_row_sum_A += val_A;
            diff = 100 - current_row_sum_A;
            
            if (diff != 0) { 
                 int c_idx = rnd.next_int_range(0, input.M - 1);
                 for(int k_fix = 0; k_fix < input.M * 2 && diff != 0; ++k_fix) { 
                    if (diff > 0) { if (current_sol.A[i][c_idx] < 100) {current_sol.A[i][c_idx]++; diff--;} }
                    else { if (current_sol.A[i][c_idx] > 0) {current_sol.A[i][c_idx]--; diff++;} }
                    c_idx = (c_idx + 1) % input.M;
                }
            }
        }
    }
    
    if (input.M > 0) { 
        best_sol = current_sol;
        current_score_val = score_calc.calculate_score(current_sol); // Evaluate score of current_sol (not best_sol)
        best_score = current_score_val;
    } else { 
        best_score = 0.0; 
    }


    double initial_temp = 5000.0; 
    if (best_score > 1.0) initial_temp = std::max(100.0, best_score * 0.05); 
    else initial_temp = std::max(100.0, initial_temp); 
    
    double final_temp = 0.1; 

    while(overall_timer.get_elapsed_seconds() < time_limit) {
        if (input.M == 0) break; 

        double progress = overall_timer.get_elapsed_seconds() / time_limit;
        double temp = initial_temp * std::pow(final_temp / initial_temp, progress * progress * progress); 
        if (temp < final_temp) temp = final_temp; 

        Solution next_sol = current_sol;
        
        double move_type_rand = rnd.next_double();
        if (move_type_rand < 0.1) { 
            int k_state = rnd.next_int_range(0, input.M - 1);
            char old_Ck = next_sol.C[k_state];
            char new_Ck = 'a' + rnd.next_int_range(0, 5); 
            if (new_Ck == old_Ck && ('f' - 'a') > 0) { 
                 new_Ck = 'a' + ( (old_Ck - 'a' + 1 + rnd.next_int_range(0,4) ) % 6 );
            }
            next_sol.C[k_state] = new_Ck;
        } else { 
            int i_state = rnd.next_int_range(0, input.M - 1);
            int j1 = rnd.next_int_range(0, input.M - 1);
            int j2 = rnd.next_int_range(0, input.M - 1);

            if (j1 == j2) { 
                if (input.M == 1) continue; 
                j2 = (j1 + 1 + rnd.next_int_range(0, input.M-2)) % input.M; 
            }
            
            int max_delta_fwd = std::min({20, next_sol.A[i_state][j1], 100 - next_sol.A[i_state][j2]});
            int max_delta_bwd = std::min({20, next_sol.A[i_state][j2], 100 - next_sol.A[i_state][j1]});

            if (max_delta_fwd <= 0 && max_delta_bwd <= 0) continue;

            int delta;
            bool forward_move = (max_delta_fwd > 0 && (max_delta_bwd <= 0 || rnd.next_double() < 0.5));

            if (forward_move) {
                 delta = rnd.next_int_range(1, max_delta_fwd);
                 next_sol.A[i_state][j1] -= delta;
                 next_sol.A[i_state][j2] += delta;
            } else if (max_delta_bwd > 0) { 
                 delta = rnd.next_int_range(1, max_delta_bwd);
                 next_sol.A[i_state][j2] -= delta; 
                 next_sol.A[i_state][j1] += delta;
            } else { 
                continue;
            }
        }
        
        double next_score_eval = score_calc.calculate_score(next_sol);

        if (next_score_eval > current_score_val || rnd.next_double() < std::exp((next_score_eval - current_score_val) / temp) ) {
            current_sol = next_sol; 
            current_score_val = next_score_eval;
            if (current_score_val > best_score) {
                 best_score = current_score_val;
                 best_sol = current_sol;
            }
        }
    }
}


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

    Timer overall_timer;
    unsigned int seed = static_cast<unsigned int>(std::chrono::system_clock::now().time_since_epoch().count());
    Random rnd(seed); 

    ProblemInput input_data;
    input_data.read();

    Solution best_sol_overall(input_data.M);
    double max_score_overall = 0.0; 
    
    double time_limit_seconds = 1.95; 
    if (input_data.L == 0 || input_data.M == 0) { 
        time_limit_seconds = 0.01; 
    }

    solve(input_data, best_sol_overall, max_score_overall, rnd, overall_timer, time_limit_seconds); 

    best_sol_overall.print();
    
    return 0;
}

Submission Info

Judge Result