fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define faster ios_base::sync_with_stdio(false); cin.tie(NULL)
  4. #define Bit(mask , i) ((mask >> i) & 1)
  5. #define fi first
  6. #define se second
  7. #define _LOG2(nl) 31 - __builtin_clz(nl)
  8. #define c_bit(nl) __builtin_popcount(nl)
  9. #define ii pair<long long , int>
  10. #define lll pair<long long , pair<long long , long long>>
  11. #define lii pair<long long , pair<long long , int>>
  12. #define iii pair<int , pair<int , int>>
  13. #define iiii pair<pair<int , int> , pair<int , int>>
  14. #define llll pair<pair<__int128 , __int128> , pair<__int128 , __int128>>
  15. #define li pair<long long , int>
  16. #define db long double
  17. #define onBit(mask , i) (mask | (1 << i))
  18. #define offBit(mask , i) (mask & (~(1 << i)))
  19.  
  20. const int N = 20;
  21. int n , t , a[N];
  22. long long f[N][N][N][N][N] , F[N][N][2][N][N][N];
  23. vector<int> Ans;
  24.  
  25. void inp(){
  26.     cin >> n >> t;
  27.     for (int i = 1 ; i <= n ; ++i){
  28.         cin >> a[i];
  29.     }
  30. }
  31.  
  32. long long dp(int pos , int val , int min1 , int min2 , int _max){
  33.     if (pos > n){
  34. //        cout << pos << " " << val << " " << min1 << " " << min2 << " " << _max << " " << 1 << '\n';
  35.         return f[pos][val][min1][min2][_max] = 1;
  36.     }
  37.  
  38.     if (f[pos][val][min1][min2][_max] != -1) return f[pos][val][min1][min2][_max];
  39.  
  40.     long long ans = 0;
  41.     bool bl = 0;
  42.     for (int j = 1 ; j <= n ; ++j){
  43.         int n_min1 = min1 , n_min2 = min2 , n_max = _max;
  44.         n_min2 = min(n_min2 , j);
  45.         if (n_min2 < n_min1) swap(n_min1 , n_min2);
  46.         n_max = max(n_max , j);
  47.  
  48.         if (n_min1 + n_min2 <= n_max) continue;
  49.  
  50.         long long tmp = dp(pos + 1 , j , n_min1 , n_min2 , n_max);
  51.  
  52.         ans += tmp;
  53.     }
  54.  
  55. //    cout << pos << " " << val << " " << min1 << " " << min2 << " " << _max << " " << ans << '\n';
  56.     return f[pos][val][min1][min2][_max] = ans;
  57. }
  58.  
  59. void DP(int pos , int val , int min1 , int min2 , int _max){
  60.     if (pos > n){
  61.         return;
  62.     }
  63.  
  64.     for (int j = 1 ; j <= n ; ++j){
  65.         int n_min1 = min1 , n_min2 = min2 , n_max = _max;
  66.         n_min2 = min(n_min2 , j);
  67.         if (n_min2 < n_min1) swap(n_min1 , n_min2);
  68.         n_max = max(n_max , j);
  69.  
  70.         if (n_min1 + n_min2 <= n_max) continue;
  71.  
  72.         if (t > f[pos + 1][j][n_min1][n_min2][n_max]){
  73.             t -= f[pos + 1][j][n_min1][n_min2][n_max];
  74.         }
  75.         else{
  76.             Ans.push_back(j);
  77.             DP(pos + 1 , j , n_min1 , n_min2 , n_max);
  78.             break;
  79.         }
  80.     }
  81. }
  82.  
  83. long long Dp(int pos , int val , int low ,  int min1 , int min2 , int _max){
  84.     if (pos > n){
  85.         return 1;
  86.     }
  87.  
  88.     if (F[pos][val][low][min1][min2][_max] != -1) return F[pos][val][low][min1][min2][_max];
  89.  
  90.     long long ans = 0;
  91.     for (int j = 1 ; j <= n ; ++j){
  92.         if (low && j > a[pos]) break;
  93.         int n_min1 = min1 , n_min2 = min2 , n_max = _max;
  94.         n_min2 = min(n_min2 , j);
  95.         if (n_min2 < n_min1) swap(n_min1 , n_min2);
  96.         n_max = max(n_max , j);
  97.  
  98.         if (n_min1 + n_min2 <= n_max) continue;
  99.  
  100.         int n_low = 0;
  101.         if (low && j == a[pos]) n_low = 1;
  102.  
  103.         ans += Dp(pos + 1 , j , n_low , n_min1 , n_min2 , n_max);
  104.     }
  105.  
  106.     return F[pos][val][low][min1][min2][_max] = ans;
  107. }
  108.  
  109. void solve(){
  110.     memset(f , -1 , sizeof f);
  111.     cout << dp(1 , 0 , n + 1 , n + 1 , 0) << '\n';
  112.     DP(1 , 0 , n + 1 , n + 1 , 0);
  113.     for (auto &c : Ans) cout << c << " ";
  114.     cout << '\n';
  115.     memset(F , -1 , sizeof F);
  116.     cout << Dp(1 , 0 , 1 , n + 1 , n + 1 , 0);
  117. }
  118.  
  119. int main(){
  120.     faster;
  121.     inp();
  122.     solve();
  123.     return 0;
  124. }
  125.  
Success #stdin #stdout 0.02s 78540KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1

1
https://ideone.com/6e6rr2
language:
C++14 (gcc 8.3)
created:
1 hour 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!