Rezumat problemă

cromatic

#4817

Fie a = (a[1], a[2], ..., a[n]) un șir de n numere întregi. Pentru fiecare k ∈ {1,2, ...,n}, definim min[k] = min{a[1], a[2], ... ,a[k]} și max[k] = max{a[1], a[2], ...,a[k]}. Astfel, asociem șirului a un alt șir de intervale închise minmax = ([min[1], max[1]], [min[2], max[2]], ..., [min[n], max[n]]). Vom spune că șirul a este un șir cromatic dacă și numai dacă elementele șirului minmax sunt distincte două câte două, adică nu există două intervale identice în șir. Dându-se un șir a, nu neapărat cromatic, să se determine:

• Numărul de șiruri cromatice NSC ce se pot forma prin rearanjarea elementelor șirului a. Întrucât acest număr poate fi foarte mare, se cere NSC modulo 1.000.000.007.
• Știind că șirul a este cromatic, să se determine poziția p ∈ {1, 2, ..., NSC} a șirului a în lista ordonată lexicografic a tuturor permutărilor cromatice ale lui a.
• Dat fiind q ∈ {1, 2, ..., NSC}, să se determine cel de-al q-lea șir cromatic în ordine lexicografică ce se poate obține prin rearanjarea elementelor șirului a.

OJI 2025, clasele 11-12

Fișiere Pracsiu Dan (dnprx) Szabo Zoltan concurs

Clasa 10 Probleme diverse Combinatorică

Rezolvă

Detalii

Problema	cromatic	Operații I/O	cromatic.in/cromatic.out
Limita timp	1.5 secunde	Limita memorie	Total: 256 MB / Stivă 64 MB
Id soluție	#63388912	Utilizator	Hustiu Teodor (teohustiu)
Fișier	cromatic.cpp	Dimensiune	4.70 KB
Data încărcării	01 Martie 2026, 14:23	Scor/rezultat	Eroare de compilare

Evaluare

Mesaj compilare

cromatic.cpp: In function 'void precompute()':
cromatic.cpp:26:63: error: 'modpow' was not declared in this scope
         inv_fact[i] = inv_fact[i - 1] * modpow(i, MOD - 2, MOD) % MOD;

                                                               ^
cromatic.cpp: In function 'void index_values(std::vector<int>&)':
cromatic.cpp:54:44: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < unique_values.size(); ++i)

                                            ^
cromatic.cpp: In function 'll count_chromatic_permutations(std::vector<int>&)':
cromatic.cpp:65:15: error: expected unqualified-id before '[' token
     for (auto [value, count] : value_count) {

               ^
cromatic.cpp:65:15: error: expected ';' before '[' token
cromatic.cpp:65:16: error: 'value' was not declared in this scope
     for (auto [value, count] : value_count) {

                ^
cromatic.cpp: In lambda function:
cromatic.cpp:65:30: error: expected '{' before ':' token
     for (auto [value, count] : value_count) {

                              ^
cromatic.cpp: In function 'll count_chromatic_permutations(std::vector<int>&)':
cromatic.cpp:65:15: error: overloaded function with no contextual type information
     for (auto [value, count] : value_count) {

               ^
cromatic.cpp:65:30: error: expected ';' before ':' token
     for (auto [value, count] : value_count) {

                              ^
cromatic.cpp:65:30: error: expected primary-expression before ':' token
cromatic.cpp:65:30: error: expected ')' before ':' token
cromatic.cpp:65:30: error: expected primary-expression before ':' token
cromatic.cpp:65:30: error: expected ';' before ':' token
cromatic.cpp:74:23: error: expected unqualified-id before '[' token
             for (auto [value, count] : value_count) {

                       ^
cromatic.cpp:74:23: error: expected ';' before '[' token
cromatic.cpp:74:24: error: 'value' was not declared in this scope
             for (auto [value, count] : value_count) {

                        ^
cromatic.cpp: In lambda function:
cromatic.cpp:74:38: error: expected '{' before ':' token
             for (auto [value, count] : value_count) {

                                      ^
cromatic.cpp: In function 'll count_chromatic_permutations(std::vector<int>&)':
cromatic.cpp:74:23: error: overloaded function with no contextual type information
             for (auto [value, count] : value_count) {

                       ^
cromatic.cpp:74:38: error: expected ';' before ':' token
             for (auto [value, count] : value_count) {

                                      ^
cromatic.cpp:74:38: error: expected primary-expression before ':' token
cromatic.cpp:74:38: error: expected ')' before ':' token
cromatic.cpp:74:38: error: expected primary-expression before ':' token
cromatic.cpp:74:38: error: expected ';' before ':' token
cromatic.cpp:82:45: error: expected ';' before ')' token
     return total_permutations - result + MOD) % MOD;

                                             ^
cromatic.cpp:82:45: error: expected primary-expression before ')' token
cromatic.cpp:82:45: error: expected ';' before ')' token
cromatic.cpp: In function 'll get_chromatic_position(std::vector<int>&)':
cromatic.cpp:94:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a.size(); ++i) {

                                ^
cromatic.cpp:102:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = i + 1; j < a.size(); ++j) {

                                        ^
cromatic.cpp: In function 'int main()':
cromatic.cpp:180:87: error: invalid initialization of reference of type 'const std::map<long long int, long long int>&' from expression of type 'std::map<int, int>'
         auto chromatic_permutation = generate_chromatic(n, q, sorted_a, value_to_index);

                                                                                       ^
cromatic.cpp:114:13: error: in passing argument 4 of 'std::vector<int> generate_chromatic(int, int, const std::vector<int>&, const std::map<long long int, long long int>&)'
 vector<int> generate_chromatic(int n, int q, const vector<int>& sorted_a, const map<ll, ll>& rank) {

             ^

Cum funcționează evaluarea?