fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <bitset>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. // Maksymalna wysokość stabilna według treści zadania to 10 000.
  9. const int MAX_VAL = 10001;
  10. bool is_stable[MAX_VAL];
  11.  
  12. int main() {
  13.     // Przyspieszenie operacji wejścia/wyjścia
  14.     ios_base::sync_with_stdio(false);
  15.     cin.tie(NULL);
  16.  
  17.     int n;
  18.     if (!(cin >> n)) return 0;
  19.  
  20.     int last_stable_input = 0;
  21.     for (int i = 0; i < n; ++i) {
  22.         int t;
  23.         cin >> t;
  24.         if (t < MAX_VAL) {
  25.             is_stable[t] = true;
  26.             last_stable_input = t;
  27.         }
  28.     }
  29.  
  30.     // reachable[i] będzie true, jeśli wysokość i można ułożyć z prętów w S
  31.     bitset<MAX_VAL> reachable;
  32.     reachable[0] = 1; // Wysokość 0 jest zawsze osiągalna (brak prętów)
  33.  
  34.     vector<int> S;
  35.     int H = 0;
  36.  
  37.     // Przechodzimy po wszystkich możliwych wysokościach
  38.     for (int i = 1; i < MAX_VAL; ++i) {
  39.         if (is_stable[i]) {
  40.             // Jeśli wysokość jest stabilna, ale nie możemy jej jeszcze ułożyć:
  41.             if (!reachable[i]) {
  42.                 // Musimy dodać i do naszego zestawu S (minimalizacja)
  43.                 S.push_back(i);
  44.  
  45.                 // Aktualizujemy osiągalne wysokości (plecak nieograniczony)
  46.                 // Używamy dekompozycji binarnej, by zachować wydajność bitsetu
  47.                 for (int k = 1; i * k < MAX_VAL; k <<= 1) {
  48.                     reachable |= (reachable << (i * k));
  49.                 }
  50.             }
  51.             // Dopóki nie napotkaliśmy błędu, aktualna stabilna wysokość 
  52.             // może być częścią bezpiecznej komory.
  53.             H = i;
  54.         } else {
  55.             // Jeśli wysokość NIE jest stabilna, a da się ją ułożyć:
  56.             if (reachable[i]) {
  57.                 // To jest pierwsza "niebezpieczna" wysokość.
  58.                 // Maksymalne bezpieczne H to i - 1.
  59.                 H = i - 1;
  60.                 break;
  61.             }
  62.         }
  63.     }
  64.  
  65.     // Dodatkowe sprawdzenie: jeśli po ostatniej stabilnej wysokości 
  66.     // jest "pusta przestrzeń", w której nic nie da się ułożyć, H może być większe.
  67.     if (H < MAX_VAL - 1 && !is_stable[H+1]) {
  68.         for (int i = H + 1; i < MAX_VAL; ++i) {
  69.             if (reachable[i]) {
  70.                 H = i - 1;
  71.                 break;
  72.             }
  73.             if (i == MAX_VAL - 1) H = MAX_VAL - 1;
  74.         }
  75.     }
  76.  
  77.     // Wypisujemy wynik: maksymalne H oraz elementy zestawu S
  78.     cout << H << "\n";
  79.     for (int s : S) {
  80.         if (s <= H) {
  81.             cout << s << "\n";
  82.         }
  83.     }
  84.  
  85.     return 0;
  86. }
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin
copy 
14
5
10
12
15
17
20
21
22
24
26
27
30
31
33
stdout
copy 
24
5
12
21
https://ideone.com/igLE8e
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!