fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct Key{
  5.     unsigned long long d,o;
  6.     bool operator==(Key const& other) const { return d==other.d && o==other.o; }
  7. };
  8. struct KeyHash{
  9.     size_t operator()(Key const& k) const {
  10.         return std::hash<unsigned long long>()(k.d*11400714819323198485ull ^ k.o);
  11.     }
  12. };
  13.  
  14. int main(){
  15.     freopen("parentheses.inp","r",stdin);
  16.     freopen("parentheses.out","w",stdout);
  17.  
  18.     vector<int> a; int x;
  19.     while (cin>>x) a.push_back(x);
  20.     int n=a.size();
  21.     if(n%2==1){ cout<<0; return 0; }
  22.  
  23.     vector<int> vals=a;
  24.     vector<int> uniq=vals;
  25.     sort(uniq.begin(),uniq.end());
  26.     uniq.erase(unique(uniq.begin(),uniq.end()),uniq.end());
  27.     int k=uniq.size();
  28.     for(int &v:vals) v=lower_bound(uniq.begin(),uniq.end(),v)-uniq.begin();
  29.  
  30.     vector<int> first(k,n), last(k,-1), cnt(k,0);
  31.     for(int i=0;i<n;i++){ first[vals[i]]=min(first[vals[i]],i); last[vals[i]]=max(last[vals[i]],i); }
  32.  
  33.     vector<unordered_map<Key, unsigned long long, KeyHash>> dp(n+1), ndp(n+1);
  34.     dp[0][{0,0}]=1;
  35.  
  36.     for(int i=0;i<n;i++){
  37.         for(int b=0;b<=n;b++) ndp[b].clear();
  38.         int v=vals[i];
  39.         unsigned long long bit=1ull<<v;
  40.         int rem=n-i-1;
  41.  
  42.         for(int b=0;b<=n;b++){
  43.             if(dp[b].empty()) continue;
  44.             for(auto &it: dp[b]){
  45.                 Key k0=it.first; unsigned long long ways=it.second;
  46.                 bool decided = (k0.d & bit);
  47.                 if(!decided){
  48.                     int nb=b+1; 
  49.                     if(nb<=rem){
  50.                         Key k1={k0.d|bit, k0.o|bit};
  51.                         if(i==last[v]){ k1.d&=~bit; k1.o&=~bit; }
  52.                         ndp[nb][k1]+=ways;
  53.                     }
  54.                     nb=b-1;
  55.                     if(nb>=0){
  56.                         Key k1={k0.d|bit, k0.o & ~bit};
  57.                         if(i==last[v]){ k1.d&=~bit; k1.o&=~bit; }
  58.                         ndp[nb][k1]+=ways;
  59.                     }
  60.                 }else{
  61.                     int nb = (k0.o & bit) ? b+1 : b-1;
  62.                     if(nb>=0 && nb<=rem){
  63.                         Key k1=k0;
  64.                         if(i==last[v]){ k1.d&=~bit; k1.o&=~bit; }
  65.                         ndp[nb][k1]+=ways;
  66.                     }
  67.                 }
  68.             }
  69.         }
  70.         dp.swap(ndp);
  71.     }
  72.  
  73.     cout << dp[0][{0,0}];
  74.     return 0;
  75. }
  76.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
0 1 2 3 4 5
stdout
copy 
Standard output is empty
https://ideone.com/nVB7I5
language:
C++14 (gcc 8.3)
created:
6 days 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!