fork download 
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. // Używamy typu long long, aby uniknąć przepełnienia przed modulo, 
  7. // chociaż przy dodawaniu intów modulo wystarczyłoby int.
  8. // Modulo z treści zadania: 10^9 + 9
  9. const long long MOD = 1000000009;
  10.  
  11. int main() {
  12.     // Optymalizacja wejścia/wyjścia dla C++ (ważne przy krótkim limicie czasu)
  13.     ios_base::sync_with_stdio(false);
  14.     cin.tie(NULL);
  15.  
  16.     int N;
  17.     if (!(cin >> N)) return 0;
  18.  
  19.     // Tablica typów dla liczb 1..2N
  20.     // 0 = C (dowolny), 1 = A (wiersz 1), 2 = B (wiersz 2)
  21.     vector<int> type(2 * N + 1, 0);
  22.  
  23.     int M;
  24.     cin >> M;
  25.     for (int i = 0; i < M; ++i) {
  26.         int val;
  27.         cin >> val;
  28.         // Zabezpieczenie na wypadek nieprawidłowych danych wejściowych, choć w zadaniach zwykle są poprawne
  29.         if (val <= 2 * N) type[val] = 1;
  30.     }
  31.  
  32.     int K;
  33.     cin >> K;
  34.     for (int i = 0; i < K; ++i) {
  35.         int val;
  36.         cin >> val;
  37.         if (val <= 2 * N) type[val] = 2;
  38.     }
  39.  
  40.     // dp[r1] = liczba sposobów na ułożenie dotychczasowych liczb,
  41.     // mając dokładnie r1 elementów w pierwszym wierszu.
  42.     // Rozmiar N+1, bo r1 może być od 0 do N.
  43.     vector<long long> dp(N + 1, 0);
  44.  
  45.     // Stan początkowy: 0 liczb wstawionych, 0 w pierwszym wierszu -> 1 sposób.
  46.     dp[0] = 1;
  47.  
  48.     // Iterujemy po liczbach od 1 do 2N
  49.     for (int k = 1; k <= 2 * N; ++k) {
  50.         vector<long long> next_dp(N + 1, 0);
  51.  
  52.         // Iterujemy po możliwych licznościach pierwszego wiersza (r1) z poprzedniego kroku
  53.         // Optymalizacja: r1 nie może być większe niż k-1 (wszystkie liczby w R1) i nie większe niż N.
  54.         int limit = min(k - 1, N);
  55.  
  56.         for (int r1 = 0; r1 <= limit; ++r1) {
  57.             if (dp[r1] == 0) continue;
  58.  
  59.             int r2 = (k - 1) - r1; // Liczba elementów w wierszu 2 przed wstawieniem k
  60.  
  61.             // Opcja 1: Wstaw k do Wiersza 1
  62.             // Warunki: k jest w A lub C, oraz mamy miejsce w wierszu 1
  63.             if ((type[k] == 1 || type[k] == 0) && r1 + 1 <= N) {
  64.                 next_dp[r1 + 1] = (next_dp[r1 + 1] + dp[r1]);
  65.                 if (next_dp[r1 + 1] >= MOD) next_dp[r1 + 1] -= MOD;
  66.             }
  67.  
  68.             // Opcja 2: Wstaw k do Wiersza 2
  69.             // Warunki: k jest w B lub C, oraz zachowujemy warunek kolumn (r2 + 1 <= r1)
  70.             // Uwaga: r2 + 1 to nowa liczba elementów w wierszu 2. Musi być <= AKTUALNEJ liczbie w wierszu 1 (r1).
  71.             if ((type[k] == 2 || type[k] == 0) && r2 + 1 <= r1) {
  72.                 next_dp[r1] = (next_dp[r1] + dp[r1]);
  73.                 if (next_dp[r1] >= MOD) next_dp[r1] -= MOD;
  74.             }
  75.         }
  76.         // Przejście do nowego stanu
  77.         dp = next_dp;
  78.     }
  79.  
  80.     // Wynikiem jest liczba sposobów, gdy mamy N elementów w wierszu 1 
  81.     // (co implikuje N elementów w wierszu 2, bo łącznie 2N)
  82.     cout << dp[N] << endl;
  83.  
  84.     return 0;
  85. }
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin 
4
2 3 2
3 4 8 7
stdout 
2
https://ideone.com/qR1CEx
language:
C++14 (gcc 8.3)
created:
16 hours 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!