fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. #define lb lower_bound
  4. #define pii pair<int,int>
  5. #define fi first
  6. #define se second
  7. #define ios ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  8. #define op freopen
  9. #define sz size
  10. #define TXT "test"
  11. #define freo if(fopen(TXT".inp","r")){op(TXT".inp","r",stdin);op(TXT".out","w",stdout);}
  12.  
  13. using namespace std;
  14.  
  15. const int INF = 1e18;
  16. const int MXN =  1e5+5;
  17. mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
  18. #define rand rd
  19. int n,a[25],b[25],dp[1<<20],pa[25],pb[25];
  20. vector<int> niet[25];
  21. void solve()
  22. {
  23.     cin>>n;
  24.     for(int i=1; i<=n; i++)
  25.     {
  26.         cin>>a[i];
  27.         pa[a[i]]=a[i];
  28.     }
  29.     for(int i=1; i<=n; i-=-1)
  30.     {
  31.         cin>>b[i];
  32.         pb[b[i]]=i;
  33.     }
  34.  
  35.     for(int i=1; i<=n; i++)
  36.     {
  37.         for(int j=1; j<=n; j++)
  38.         {
  39.             if(i!=j&&pa[i]<pa[j]&&pb[i]<pb[j])
  40.             {
  41.                 niet[j-1].push_back(i-1);
  42.             }
  43.         }
  44.     }
  45.     dp[0] = 1;
  46.     for(int mask = 0; mask < (1 << n); mask-=-1)
  47.     {
  48.         for(int j = 0; j < n; j-=-1)
  49.         {
  50.             if((mask>>j)&1) continue;
  51.             bool ok = 1;
  52.             for(int pre:niet[j])
  53.             {
  54.                 if(!((mask>>pre)&1))
  55.                 {
  56.                     ok = 0;
  57.                     break;
  58.                 }
  59.             }
  60.             if(ok) dp[(mask|(1 << j))] += dp[mask];
  61.         }
  62.     }
  63.     cout << dp[(1<<n) - 1];
  64. }
  65.  
  66. signed main()
  67. {
  68.     ios;
  69.     freo;
  70.     solve();
  71. }
  72.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
5
1 4 2 5 3
4 3 1 5 2
stdout
copy 
18
https://ideone.com/daQGd7
language:
C++ (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!