fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using U64 = unsigned long long;
  5.  
  6. int main(){
  7.     //freopen("parentheses.inp","r",stdin);
  8.     //freopen("parentheses.out","w",stdout);
  9.     ios::sync_with_stdio(false);
  10.     cin.tie(nullptr);
  11.  
  12.     vector<int> a; int x;
  13.     while (cin>>x) a.push_back(x);
  14.     int n=a.size();
  15.     if(n%2){ cout<<0; return 0; }
  16.  
  17.     vector<int> vals=a, uniq=a;
  18.     sort(uniq.begin(),uniq.end());
  19.     uniq.erase(unique(uniq.begin(),uniq.end()),uniq.end());
  20.     int k=uniq.size();
  21.     for(int &v:vals) v=int(lower_bound(uniq.begin(),uniq.end(),v)-uniq.begin());
  22.  
  23.     vector<vector<int>> pos(k);
  24.     for(int i=0;i<n;i++) pos[vals[i]].push_back(i);
  25.  
  26.     vector<int> multi_id(k,-1);
  27.     vector<vector<int>> groups;
  28.     vector<int> single_pos;
  29.     for(int c=0;c<k;c++){
  30.         if((int)pos[c].size()>=2){
  31.             multi_id[c]=(int)groups.size();
  32.             groups.push_back(pos[c]);
  33.         }else{
  34.             single_pos.push_back(pos[c][0]);
  35.         }
  36.     }
  37.     int m=groups.size();
  38.     int r=single_pos.size();
  39.  
  40.     vector<int> who(n,-1), forced_dir(n,0);
  41.     for(int g=0;g<m;g++) for(int p:groups[g]) who[p]=g;
  42.     U64 ans=0;
  43.  
  44.     vector<int> gsize(m);
  45.     for(int g=0;g<m;g++) gsize[g]=(int)groups[g].size();
  46.  
  47.     vector<int> openCnt(1<<min(m,25),0); // placeholder to avoid realloc
  48.  
  49.     if(m==0){
  50.         vector<U64> dp(n+1,0), ndp(n+1,0);
  51.         dp[0]=1;
  52.         for(int i=0;i<n;i++){
  53.             int rem=n-i-1;
  54.             fill(ndp.begin(),ndp.end(),0);
  55.             for(int b=0;b<=n;b++) if(dp[b]){
  56.                 if(b+1<=rem) ndp[b+1]+=dp[b];
  57.                 if(b-1>=0)   ndp[b-1]+=dp[b];
  58.             }
  59.             dp.swap(ndp);
  60.         }
  61.         cout<<dp[0];
  62.         return 0;
  63.     }
  64.  
  65.     vector<int> forced(n,0);
  66.     for(int mask=0; mask<(1<<m); ++mask){
  67.         int fixedOpens=0;
  68.         for(int g=0;g<m;g++) if(mask>>g & 1) fixedOpens+=gsize[g];
  69.         int needOpen = n/2 - fixedOpens;
  70.         if(needOpen<0 || needOpen>r) continue;
  71.         for(int i=0;i<n;i++){ forced[i]=0; }
  72.         for(int g=0;g<m;g++){
  73.             int dir = (mask>>g)&1 ? 1 : -1;
  74.             for(int p:groups[g]) forced[p]=dir;
  75.         }
  76.         vector<U64> dp(n+1,0), ndp(n+1,0);
  77.         dp[0]=1;
  78.         int freeOpensLeft=needOpen;
  79.         for(int i=0;i<n;i++){
  80.             int rem=n-i-1;
  81.             fill(ndp.begin(),ndp.end(),0);
  82.             if(forced[i]==1){
  83.                 for(int b=0;b<=n;b++) if(dp[b]){
  84.                     if(b+1<=rem) ndp[b+1]+=dp[b];
  85.                 }
  86.             }else if(forced[i]==-1){
  87.                 for(int b=0;b<=n;b++) if(dp[b]){
  88.                     if(b-1>=0) ndp[b-1]+=dp[b];
  89.                 }
  90.             }else{
  91.                 for(int b=0;b<=n;b++) if(dp[b]){
  92.                     if(b+1<=rem && freeOpensLeft>0) ndp[b+1]+=dp[b];
  93.                     if(b-1>=0) ndp[b-1]+=dp[b];
  94.                 }
  95.                 freeOpensLeft--;
  96.             }
  97.             dp.swap(ndp);
  98.         }
  99.         ans+=dp[0];
  100.     }
  101.  
  102.     cout<<ans;
  103.     return 0;
  104. }
  105.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
0 0 1 2 3 4
stdout 
1
https://ideone.com/u9CL8W
language:
C++14 (gcc 8.3)
created:
7 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!