#1083875 (C++17) No.1281 Cigarette Distribution

• 問題: No.1281 Cigarette Distribution
• ユーザー: qwewe
• 提出日時: 2025-05-14 13:06:42
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: TLE
• 実行時間: -
• コード長: 7,871 bytes
• コンパイル時間: 1,019 ms
• コンパイル使用メモリ: 97,752 KB
• 実行使用メモリ: 16,064 KB
• 最終ジャッジ日時: 2025-05-14 13:08:08
• 合計ジャッジ時間: 5,044 ms
• ジャッジサーバーID （参考情報）: judge5 / judge2

ファイルパターン	結果
other	AC * 12 TLE * 1 -- * 10

ソースコード

#include <iostream>
#include <vector>
#include <numeric>
#include <map>
#include <set>
#include <vector>
#include <algorithm>

// Function to calculate the product of counts modulo MOD
// Takes the vector of counts and the number of boxes X as input
long long calculate_goodness(const std::vector<long long>& counts, int X) {
    long long product = 1;
    long long MOD = 1e9 + 7; // The modulus value
    bool has_zero = false; // Flag to check if any box count is zero

    // Iterate through all X boxes
    for (int i = 0; i < X; ++i) {
        if (counts[i] == 0) {
            // If any box has 0 cigarettes, the product ("goodness") is 0
            has_zero = true;
            break; // No need to check further boxes
        }
        // Multiply the current product by the count of cigarettes in the box, modulo MOD
        product = (product * counts[i]) % MOD;
    }

    if (has_zero) {
        return 0; // Return 0 if any box was empty
    }
    return product; // Return the final product modulo MOD
}

int main() {
    // Use faster I/O operations
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int N; // Number of steps (operations)
    int M_limit; // Maximum number of boxes X to calculate for
    std::cin >> N >> M_limit; // Read N and M

    long long MOD = 1e9 + 7; // Modulo value defined in the problem

    // Iterate through each required number of boxes X from 1 to M_limit
    for (int X = 1; X <= M_limit; ++X) {
        
        // Initialize the state for X boxes
        std::vector<long long> counts(X, 0); // Stores counts for each box, index 0 to X-1. Initially all 0.
        
        // Data structure to efficiently find boxes with minimum counts.
        // Maps count value to a set of box indices having that count.
        // Using std::map ensures counts are ordered, so map.begin() gives the minimum count.
        // Using std::set for indices ensures indices are ordered, useful for tie-breaking (smallest index).
        std::map<long long, std::set<int>> counts_map; 
        
        // Set to keep track of indices of boxes that are currently empty (count = 0).
        std::set<int> empty_boxes;
        // Initially, all X boxes are empty. Fill the set.
        for (int i = 0; i < X; ++i) {
            empty_boxes.insert(i);
        }

        // Simulate the N steps of adding and removing cigarettes
        for (int step = 0; step < N; ++step) {
            // A-kun's move: Add 2 cigarettes based on strategy
            int target_idx = -1; // The index of the box A-kun chooses to add cigarettes to

            // A-kun's strategy: Prioritize filling empty boxes.
            if (!empty_boxes.empty()) {
                // If there are empty boxes, A picks one (smallest index due to set iteration properties).
                target_idx = *empty_boxes.begin(); // Get the smallest index of an empty box.
                empty_boxes.erase(empty_boxes.begin()); // Remove this box index from the empty set.
                
                // This box now receives 2 cigarettes (goes from 0 to 2).
                counts[target_idx] = 2;
                counts_map[2].insert(target_idx); // Add this box to the map under count 2.

            } else {
                 // If there are no empty boxes, A picks a box with the minimum count.
                 // Defensive check: If counts_map is empty, it implies there are no non-empty boxes.
                 // This state should not be reachable under normal operation if X > 0.
                 if (counts_map.empty()) { 
                     continue; // Skip step if state is invalid.
                 }
                
                // Get the minimum count present among non-empty boxes.
                long long min_count = counts_map.begin()->first; 
                // Get the smallest index among boxes with this minimum count.
                target_idx = *counts_map[min_count].begin(); 
                
                // Remove the chosen box from the set associated with its current count (min_count).
                counts_map[min_count].erase(counts_map[min_count].begin());
                // If this set becomes empty, remove the count entry from the map to keep it clean.
                if (counts_map[min_count].empty()) {
                    counts_map.erase(min_count); 
                }
                
                // Update the box's count (increases by 2).
                counts[target_idx] = min_count + 2;
                // Add the box index to the set associated with its new count (min_count + 2).
                counts_map[min_count + 2].insert(target_idx);
            }

            // B-kun's move: Remove 1 cigarette based on strategy
            int remove_idx = -1; // The index of the box B-kun chooses to remove a cigarette from

            // Check if there are any boxes with exactly 1 cigarette. Use find for efficiency.
            auto it_map = counts_map.find(1); 
            if (it_map != counts_map.end() && !it_map->second.empty()) {
                 // B-kun's priority: If boxes with count 1 exist, target one of them to minimize goodness (to 0).
                 remove_idx = *it_map->second.begin(); // Get the smallest index box with count 1.

                 // Remove this box from the count 1 set in the map.
                 it_map->second.erase(it_map->second.begin());
                 // If the set for count 1 becomes empty, remove the count 1 entry from the map.
                 if (it_map->second.empty()) {
                    counts_map.erase(it_map); 
                 }
                 
                 // The count of this box becomes 0.
                 counts[remove_idx] = 0;
                 empty_boxes.insert(remove_idx); // Add this box index back to the set of empty boxes.

            } else {
                 // If no boxes have count 1, B targets a box with the minimum positive count (which must be >= 2).
                 if (counts_map.empty()) {
                     // If counts_map is empty, it means all boxes are empty. B cannot move.
                     continue; 
                 }

                 // Find the minimum count among non-empty boxes. Since the count 1 case is handled, this count must be >= 2.
                 long long min_pos_count = counts_map.begin()->first;
                 
                 // Defensive check: the minimum count must be positive.
                 if (min_pos_count <= 0) { 
                     continue; // Skip B's move if state seems invalid.
                 }

                 // Get the smallest index box with this minimum count.
                 remove_idx = *counts_map.begin()->second.begin(); 

                 // Remove this box from the set associated with its current count (min_pos_count).
                 counts_map.begin()->second.erase(counts_map.begin()->second.begin());
                 // If this set becomes empty, remove the count entry from the map.
                 if (counts_map.begin()->second.empty()) {
                     counts_map.erase(counts_map.begin()); 
                 }

                 // Update the box's count (decreases by 1).
                 counts[remove_idx] = min_pos_count - 1;
                 
                 // Add the box index to the set associated with its new count.
                 // Since min_pos_count >= 2, the new count `min_pos_count - 1` is >= 1.
                 // The box remains non-empty.
                 counts_map[counts[remove_idx]].insert(remove_idx);
            }
        }
        
        // After N steps, calculate the final "goodness" using the helper function.
        long long final_goodness = calculate_goodness(counts, X);
        // Output the result for the current value of X.
        std::cout << final_goodness << "\n";
    }

    return 0; // Indicate successful execution.
}