oj.uz

Submission #332235

# Submission time Handle Problem Language Result Execution time Memory
332235 2020-12-01T18:20:38 Z AlexPop28 Fishing Game (RMI19_fishing) C++11
100 / 100
 232 ms 191232 KB 
#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 (ab == 0 && ca == 0) { // A passes one of his cards to B (unless A doesn't have any)
      Upd(DP(ab, bc, ca, 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 (bc == 0 && ab == 0) {
      Upd(DP(ab, bc, 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)));
    }
    if (ca == 0 && bc == 0 && discarded) {
      Upd(DP(ab, bc, 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
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 191232 KB Output is correct
2 Correct 101 ms 191084 KB Output is correct
3 Correct 101 ms 191084 KB Output is correct
4 Correct 102 ms 191084 KB Output is correct
5 Correct 117 ms 191032 KB Output is correct
6 Correct 129 ms 191092 KB Output is correct
7 Correct 147 ms 191228 KB Output is correct
8 Correct 172 ms 191104 KB Output is correct
9 Correct 200 ms 191084 KB Output is correct
10 Correct 232 ms 191100 KB Output is correct