oj.uz

Submission #645326

# Submission time Handle Problem Language Result Execution time Memory
645326 2022-09-26T19:25:18 Z Alex_tz307 Fishing Game (RMI19_fishing) C++17
100 / 100
 586 ms 27860 KB 
#include <bits/stdc++.h>

using namespace std;

const int mod = 1e9 + 7;
const int kN = 100;
int n, dp[2 * kN][2 * kN][2 * kN];
bitset<3 * kN> a[3];

/// dp[i][j][k] =def= numarul de modalitati distincte de desfasurare ale jocului astfel inca A si B
///                   au in comun la inceput i carti, B si C au j carti, iar C si A au k carti
/// Se observa ca 2 * (i + j + k) este numarul total de carti de pe masa(duplicatele pe care le
/// detine oricine la inceput trebuie eliminate). De asemenea, la fiecare runda a jocului
/// aceasta cantitate va trebui redusa si va fi redusa cu un numar de 2 * p carti(o pereche este
/// eliminata "impreuna", deci asta ne permite de acum sa impartim totul la 2).
/// Sa fixam toate tipurile de interactiuni ce pot avea loc intre A si B intr-o runda. Celelalte 2
/// cazuri vor fi simetrice:
/// (1) A nu are ce carte sa ii dea lui B. In acest caz, i + k = 0(A si B, respectiv A si C nu pot
///     avea carti comune daca A nu are carti deloc).
/// (2) A ii da lui B o carte pe care o au cei 2 in comun. => i variante de a face asta, iar i scade
///     in urma acestei operatii pentru ca A nu mai detine cartea oferita.
/// (3) A ii da lui B o carte pe care o are in comun cu C. => k variante de a face asta, iar j creste
///     si k scade dupa aceasta operatie(C si A au o carte in minus in comun, iar B si C una in plus).
/// Se observa ca suma ramane constanta dupa o operatie de tipul (1) sau (3), deci orice runda trebuie
/// sa contina cel putin o operatie de tipul 2 pentru a satisface conditia din enunt.
/// De asemenea, pentru ca in fiecare runda trebuie ca numarul total de carti sa scada, starile
/// trebuie considerate in ordinea totalului i + j + k.

void addSelf(int &x, int y) {
  x += y;
  if (x >= mod) {
    x -= mod;
  }
}

int mult(int x, int y) {
  return (int64_t)x * y % mod;
}

void apply1(int &ways, int i, int j, int k) {
  if (i + k != 0) {
    ways = 0;
  }
}

void apply2(int &ways, int &i, int j, int k) {
  ways *= i;
  i -= 1;
}

void apply3(int &ways, int i, int &j, int &k) {
  ways *= k;
  j += 1;
  k -= 1;
}

void precalc() {
  dp[0][0][0] = 1;

  for (int total = 1; total <= 6 * n; ++total) {
    for (int i = 0; i <= 2 * n && i <= total; ++i) {
      for (int j = 0; j <= 2 * n && i + j <= total && i + j <= 3 * n; ++j) {

        int k = total - i - j;

        if (i + k > 3 * n || j + k > 3 * n) {
          continue;
        }

        for (int ab = 1; ab <= 3; ++ab) {
          for (int bc = 1; bc <= 3; ++bc) {
            for (int ca = 1; ca <= 3; ++ca) {

              if (ab != 2 && bc != 2 && ca != 2) {
                continue;
              }

              int ways = 1, newI = i, newJ = j, newK = k;

              if (ab == 1) {
                apply1(ways, newI, newJ, newK);
              } else if (ab == 2) {
                apply2(ways, newI, newJ, newK);
              } else {
                apply3(ways, newI, newJ, newK);
              }
              if (ways == 0 || newI < 0 || newJ < 0 || newK < 0) {
                continue;
              }

              if (bc == 1) {
                apply1(ways, newJ, newK, newI);
              } else if (bc == 2) {
                apply2(ways, newJ, newK, newI);
              } else {
                apply3(ways, newJ, newK, newI);
              }
              if (ways == 0 || newI < 0 || newJ < 0 || newK < 0) {
                continue;
              }

              if (ca == 1) {
                apply1(ways, newK, newI, newJ);
              } else if (ca == 2) {
                apply2(ways, newK, newI, newJ);
              } else {
                apply3(ways, newK, newI, newJ);
              }
              if (ways == 0 || newI < 0 || newJ < 0 || newK < 0) {
                continue;
              }

              addSelf(dp[i][j][k], mult(ways, dp[newI][newJ][newK]));
            }
          }
        }
      }
    }
  }
}

void testCase() {
  for (int i = 0; i < 3; ++i) {
    a[i].reset();
    for (int j = 0; j < 2 * n; ++j) {
      int x;
      cin >> x;
      a[i][x] = true;
    }
  }

  int ab = (a[0] & a[1]).count(), bc = (a[1] & a[2]).count(), ca = (a[2] & a[0]).count();
  cout << dp[ab][bc][ca] << '\n';
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int tests;
  cin >> n >> tests;
  precalc();
  for (int tc = 0; tc < tests; ++tc) {
    testCase();
  }
  return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 6 ms 1620 KB Output is correct
5 Correct 75 ms 7628 KB Output is correct
6 Correct 132 ms 10768 KB Output is correct
7 Correct 235 ms 14424 KB Output is correct
8 Correct 316 ms 18664 KB Output is correct
9 Correct 489 ms 23300 KB Output is correct
10 Correct 586 ms 27860 KB Output is correct