Submission #332233

#	Time	Username	Problem	Language	Result	Execution time	Memory
332233		AlexPop28	Fishing Game (RMI19_fishing)	C++11	0 / 100	253 ms	191164 KiB

fishing

#include <bits/stdc++.h>
#define dbg() cerr <<
#define name(x) (#x) << ": " << (x) << ' ' <<

using namespace std;

void Read(vector<int> &v) {
  for (int &x : v) cin >> x; 
}

int CountPairs(const vector<int> &a, const vector<int> &b) {
  int ans = 0; for (auto &x : a) for (auto &y : b) ans += x == y; return ans;
}

const int MOD = (int)1e9 + 7;
const int N = 100;

int Add(int a, int b) {
  a += b;
  if (a >= MOD) a -= MOD;
  if (a < 0) a += MOD;
  return a;
}

int Mul(int a, int b) {
  return 1LL * a * b % MOD;
}

int dp[2 * N + 1][2 * N + 1][2 * N + 1][3][2];

int DP(int ab, int bc, int ca, int pos, bool discarded) {
  int &curr = dp[ab][bc][ca][pos][discarded];
  if (curr != -1) return curr;
  if (ab == 0 && bc == 0 && ca == 0) return 1;

  curr = 0;

  auto Upd = [&](int val) {
    curr = Add(curr, val);
  };

  if (pos == 0) {
    if (ab > 0) {
      Upd(Mul(ab, DP(ab - 1, bc, ca, 1, true))); 
    }
    if (ca > 0) {
      Upd(Mul(ca, DP(ab, 1 + bc, ca - 1, 1, false)));
    }
  }

  if (pos == 1) {
    if (bc > 0) {
      Upd(Mul(bc, DP(ab, bc - 1, ca, 2, true)));
    }
    if (ab > 0) {
      Upd(Mul(ab, DP(ab - 1, bc, 1 + ca, 2, discarded)));
    }
  }

  if (pos == 2) {
    if (ca > 0) {
      Upd(Mul(ca, DP(ab, bc, ca - 1, 0, false)));
    }
    if (bc > 0 && discarded) {
      Upd(Mul(bc, DP(1 + ab, bc - 1, ca, 0, false)));
    }
  }

  // dbg() name(ab) name(bc) name(ca) name(pos) name(discarded) name(curr) endl;
  return curr;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  memset(dp, -1, sizeof(dp));

  int n, t; cin >> n >> t;
  while (t--) {
    vector<int> a(2 * n), b(2 * n), c(2 * n);
    Read(a); Read(b); Read(c);

    int ab = CountPairs(a, b);
    int bc = CountPairs(b, c);
    int ca = CountPairs(c, a);

//    dbg() name(ab) name(bc) name(ca) endl;
    cout << DP(ab, bc, ca, 0, false) << '\n';
  }
}

• Subtask 1: 0 / 100