fork download 
  1. //#pragma GCC optimize("Ofast,unroll-loops")
  2. //#pragma GCC target("avx2,tune=native")
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. #define file "parentheses"
  7.  
  8. using ll = long long;
  9. using vi = vector<int>;
  10.  
  11. inline void rf(){
  12.     ios::sync_with_stdio(false);
  13.     cin.tie(nullptr); cout.tie(nullptr);
  14.     if (fopen(file".inp","r")){
  15.         freopen(file".inp","r",stdin);
  16.         freopen(file".out","w",stdout);
  17.     }
  18. }
  19.  
  20.  
  21. int main() {
  22.     rf();
  23.  
  24.     string line;
  25.     if(!getline(cin, line)){ cout << 0 << "\n"; return 0; }
  26.     stringstream ss(line);
  27.     vector<int> cvec; int v;
  28.     while (ss >> v) cvec.push_back(v);
  29.     int n = (int)cvec.size();
  30.     if(n==0 || (n&1)){ cout << 0 << "\n"; return 0; }
  31.  
  32.     map<int, vector<int>> pos;
  33.     for (int i=0;i<n;i++) pos[cvec[i]].push_back(i+1);
  34.  
  35.     vector<vector<int>> groups;
  36.     vector<int> singles;
  37.     for (auto &p: pos) {
  38.         if ((int)p.second.size() >= 2) groups.push_back(p.second);
  39.         else singles.push_back(p.second[0]);
  40.     }
  41.     sort(singles.begin(), singles.end());
  42.  
  43.     int m = (int)groups.size();
  44.     int k = (int)singles.size();
  45.     if (m > 25){ cout << 0 << "\n"; return 0; }
  46.  
  47.     vector<int> boundary; boundary.push_back(0);
  48.     for(int x: singles) boundary.push_back(x);
  49.     boundary.push_back(n+1);
  50.     int B = (int)boundary.size()-1;
  51.  
  52.     auto build_segments = [&](const vi &delta, vi &segSum, vi &segLow)->bool{
  53.         segSum.assign(B,0); segLow.assign(B,0);
  54.         for (int t=0;t<B;t++){
  55.             int L=boundary[t], R=boundary[t+1];
  56.             int cur=0, mn=0, sum=0;
  57.             for(int i=L+1;i<=R-1;i++){
  58.                 cur += delta[i]; sum += delta[i];
  59.                 if(cur < mn) mn = cur;
  60.                 if(t==0 && cur<0) return false;
  61.             }
  62.             segSum[t]=sum; segLow[t]=mn;
  63.         }
  64.         return true;
  65.     };
  66.  
  67.     vector<int> gsize(m);
  68.     for(int i=0;i<m;i++) gsize[i]=(int)groups[i].size();
  69.  
  70.     vector<int> order(m); iota(order.begin(), order.end(), 0);
  71.     sort(order.begin(), order.end(),
  72.          [&](int a,int b){ return groups[a].back() < groups[b].back(); });
  73.  
  74.     vector<int> suf(m+1,0);
  75.     for(int i=m-1;i>=0;--i) suf[i]=suf[i+1]+gsize[order[i]];
  76.  
  77.     int open_min = max(0, n/2 - k), open_max = n/2;
  78.  
  79.     vi delta(n+2,0), segSum, segLow;
  80.     ll ans = 0;
  81.  
  82.     function<void(int,int)> dfs = [&](int idx, int open_fixed){
  83.         if(open_fixed>open_max) return;
  84.         if(open_fixed + suf[idx] < open_min) return;
  85.  
  86.         if(idx==m){
  87.             int need = n/2 - open_fixed;
  88.             if(need<0 || need>k) return;
  89.  
  90.             if(!build_segments(delta, segSum, segLow)) return;
  91.  
  92.             if(k==0){ ans += (segSum[0]==0); return; }
  93.             if(segLow[0]<0) return;
  94.  
  95.             static ll dp[2][55][26];
  96.             for(int a=0;a<2;a++) for(int b=0;b<=n;b++) for(int t=0;t<=need;t++) dp[a][b][t]=0;
  97.             int cur=0,nxt=1; dp[cur][segSum[0]][0]=1;
  98.  
  99.             for(int i=0;i<k;i++){
  100.                 for(int b=0;b<=n;b++) for(int t=0;t<=need;t++) dp[nxt][b][t]=0;
  101.                 int segId=i+1;
  102.                 for(int bal=0; bal<=n; ++bal){
  103.                     for(int t=0; t<=need; ++t){
  104.                         ll ways=dp[cur][bal][t];
  105.                         if(!ways) continue;
  106.                         if(t<need){
  107.                             int b1=bal+1;
  108.                             if(b1+segLow[segId]>=0){
  109.                                 int b2=b1+segSum[segId];
  110.                                 if(0<=b2 && b2<=n) dp[nxt][b2][t+1]+=ways;
  111.                             }
  112.                         }
  113.                         if(bal>0){
  114.                             int b1=bal-1;
  115.                             if(b1+segLow[segId]>=0){
  116.                                 int b2=b1+segSum[segId];
  117.                                 if(0<=b2 && b2<=n) dp[nxt][b2][t]+=ways;
  118.                             }
  119.                         }
  120.                     }
  121.                 }
  122.                 swap(cur,nxt);
  123.             }
  124.             int tailId=k; ll add=0;
  125.             for(int bal=0; bal<=n; ++bal){
  126.                 ll ways=dp[cur][bal][need];
  127.                 if(!ways) continue;
  128.                 if(bal+segLow[tailId]>=0 && bal+segSum[tailId]==0) add+=ways;
  129.             }
  130.             ans+=add;
  131.             return;
  132.         }
  133.  
  134.         int g = order[idx];
  135.  
  136.         for(int p: groups[g]) delta[p]+=1;
  137.         dfs(idx+1, open_fixed + gsize[g]);
  138.         for(int p: groups[g]) delta[p]-=1;
  139.  
  140.         for(int p: groups[g]) delta[p]-=1;
  141.         dfs(idx+1, open_fixed);
  142.         for(int p: groups[g]) delta[p]+=1;
  143.     };
  144.  
  145.     dfs(0,0);
  146.     cout << ans << "\n";
  147.     return 0;
  148. }
  149.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin 
0 1 2 3 4 5
stdout 
5
https://ideone.com/SSBb0o
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!