fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define FOR(i, a, b) for (int i = a; i <= b; ++i)
  4. #define FORD(i, a, b) for (int i = a; i >= b; --i)
  5. #define ll long long
  6. #define MASK(x) (1 << x)
  7.  
  8. using namespace std;
  9.  
  10. const int N = 55;
  11. int a[N], n, m, cntL[N], cntR[N], id[N];
  12. int value[N], idx;
  13. int cnt[MASK(25)];
  14. vector<int> mask[2][N];
  15.  
  16. void nhap() {
  17.     int x;
  18.     vector<int> vec;
  19.     while (cin >> x) vec.push_back(x);
  20.     n = vec.size();
  21.     FOR(i, 1, n) a[i] = vec[i - 1];
  22. }
  23.  
  24. int OR(int a, int b) {
  25.     if (b == -1) return a;
  26.     return a | MASK(b);
  27. }
  28.  
  29. void dfs1(int pos, int delta, int msk) {
  30.     if (delta < 0) return ;
  31.     if (pos == m + 1) {
  32.         mask[0][delta].push_back(msk);
  33.         return ;
  34.     }
  35.  
  36.     if (value[a[pos]]) dfs1(pos + 1, delta + value[a[pos]], msk);
  37.     else {
  38.         value[a[pos]] = 1;
  39.         dfs1(pos + 1, delta + value[a[pos]], OR(msk, id[a[pos]]));
  40.         value[a[pos]] = -1;
  41.         dfs1(pos + 1, delta + value[a[pos]], msk);
  42.         value[a[pos]] = 0;
  43.     }
  44. }
  45.  
  46. void dfs2(int pos, int delta, int msk) {
  47.     if (delta > 0) return ;
  48.     if (pos == m) {
  49.         mask[1][-delta].push_back(msk);
  50.         return ;
  51.     }
  52.  
  53.     if (value[a[pos]]) dfs2(pos - 1, delta + value[a[pos]], msk);
  54.     else {
  55.         value[a[pos]] = 1;
  56.         dfs2(pos - 1, delta + value[a[pos]], OR(msk, id[a[pos]]));
  57.         value[a[pos]] = -1;
  58.         dfs2(pos - 1, delta + value[a[pos]], msk);
  59.         value[a[pos]] = 0;
  60.     }
  61. }
  62.  
  63. void giai() {
  64.     m = n / 2;
  65.     memset(id, -1, sizeof id);
  66.     memset(cntL, 0, sizeof cntL);
  67.     memset(cntR, 0, sizeof cntR);
  68.     memset(cnt, 0, sizeof cnt);
  69.     idx = 0;
  70.  
  71.     FOR(i, 1, m) ++cntL[a[i]];
  72.     FOR(i, m + 1, n) ++cntR[a[i]];
  73.  
  74.     FOR(i, 0, n - 1)
  75.         if (cntL[i] && cntR[i] && id[i] == -1) id[i] = idx++;
  76.  
  77.     dfs1(1, 0, 0);
  78.     dfs2(n, 0, 0);
  79.  
  80.     ll ans = 0;
  81.     FOR(i, 0, m) {
  82.         for (int x : mask[0][i]) ++cnt[x];
  83.         for (int x : mask[1][i]) ans += cnt[x];
  84.         for (int x : mask[0][i]) --cnt[x];
  85.     }
  86.  
  87.     cout << ans;
  88. }
  89.  
  90. int main() {
  91.     ios_base::sync_with_stdio(0);
  92.     cin.tie(0); cout.tie(0);
  93.  
  94.     #define name "parentheses"
  95.  
  96.     if (fopen(name".inp", "r")) {
  97.         freopen(name".inp", "r", stdin);
  98.         freopen(name".out", "w", stdout);
  99.     }
  100.  
  101.     nhap();
  102.     giai();
  103.  
  104.     return 0;
  105. }
  106.  
Success #stdin #stdout 0.03s 134664KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/RmUcT2
language:
C++14 (clang 8.0)
created:
6 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!