SRM453 Div1 Easy TheBasketballDivOne

gistfile1.txt

class TheBasketballDivOne {
  set<vector<int> > s;
  int n,m;

  void check_and_insert(vector<vector<bool> > &v){
    vector<int> v2;
    for(int i = 0; i < n; i++){
      int cnt = 0;
      for(int j = 0; j < 2*n; j++){
        if(v[i][j]) cnt++;
      }
      v2.push_back(cnt);
    }
    sort(v2.begin(),v2.end(),greater<int>());
    if(v2[0] != m) return;
    s.insert(v2);
  }

  bool prune(vector<vector<bool> > &v){
    int cnt = 0;
    for(int i = 0; i < 2 * n; i++){
      if(v[0][i]) cnt++;
    }
    if(cnt == m) return false;
    return true;
  }

  void rec(int i, int j, vector<vector<bool> > &v){
    if(j == n){
      check_and_insert(v);
      return;
    }
    if(i == 2 * n){
      if(j == 0 && prune(v)) return;
      rec(0,j+1,v);
      return;
    }
    if(i < 2 * (j + 1)){
      rec(i+1,j,v);
      return;
    }
    int inv_i = i / 2;
    int inv_j = 2 * j + i % 2;
    v[j][i] = true;
    v[inv_i][inv_j] = false;
    rec(i+1,j,v);
    v[j][i] = false;
    v[inv_i][inv_j] = true;
    rec(i+1,j,v);

    return;
  }

public:
   int find( int nn, int mm ) {
     n = nn;
     m = mm;
     s.clear();
     vector<vector<bool> > v(n);
     for(int i = 0; i < n; i++){
       v.resize(2*n);
       for(int j = 0; j < 2*n; j++){
         v[i][j] = false;
       }
     }
     rec(0,0,v);
     return s.size();
   }
};