Submission #1220650

---

Source Code Expand

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <cassert>
using namespace std;

#define sz(a) int((a).size())
#define rep(i, s, n)  for(int i = s; i <= (n); ++i)
#define rev(i, n, s)  for(int i = (n); i >= s; --i)
#define fore(x, a) for(auto &&x : a)
typedef long long ll;
const int mod = 1000000007;
const int N = 105;

//map<pair<pair<int, int>, set<int>>, int> dp;
int dp[N][N][N];
int a[N];
int n;

/*
int go(int p, set<int> b, int prev) {
  if(p == 0) {
    return 1;
  }
  if(dp.find(make_pair(make_pair(p, prev), b)) != dp.end()) {
    return dp[make_pair(make_pair(p, prev), b)];
  }
  int &res = dp[make_pair(make_pair(p, prev), b)];
  res = 0;
  b.insert(a[p]);
  b.insert(a[2 * n - p]);
  fore(y, b) {
    set<int> c;
    for(set<int>::iterator it = b.begin(); it != b.end(); it++) {
        int x = *it;
        if((prev < x && x < y) || (y < x && x < prev)) {
          continue;
        } else {
          c.insert(x);
        }
      }
    res += go(p - 1, c, y);
    if(res >= mod) {
      res -= mod;
    }
  }
  return res;
}
*/

int go(int p, int b, int prev) {
  if(p == 0) {
    return 1;
  }
  int &res = dp[p][b][prev];
  if(res == -1) {
    res = 0;
    if(p != n) {
      if(a[p] != a[p + 1]) {
        b++;
        prev++;
      }
      if(a[2 * n - p] != a[2 * n - p - 1]) {
        b++;
      }
    }
    rep(y, 1, b) {
      int newb = b, newprev = prev;
      if(y > prev) {
        newb -= (y - prev - 1);
        newprev = prev + 1;
      }
      if(prev > y) {
        newb -= (prev - y - 1);
        newprev = y;
      }
      res += go(p - 1, newb, newprev);
      if(res >= mod) {
        res -= mod;
      }
    }
  }
  return res;
}

int main() {
#ifdef loc
  if(!freopen((string(FOLDER) + "inp.txt").c_str(), "r", stdin)) {
    assert(0);
  }
  freopen((string(FOLDER) + "out.txt").c_str(), "w", stdout);
#endif
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  rep(i, 1, 2 * n - 1) {
    cin >> a[i];
  }
  sort(a + 1, a + 2 * n);
  /*
  set<int> cands;
  cout << go(n, cands, a[n]) << endl;
  */
  memset(dp, -1, sizeof(dp));
  cout << go(n, 1, 1) << endl;
  return 0;
}

Submission Info

Judge Result