結果
| 問題 |
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.
}