Submission #345957

# Submission time Handle Problem Language Result Execution time Memory
345957 2021-01-08T16:33:14 Z jacynkaa Fishing Game (RMI19_fishing) C++14
100 / 100
681 ms 114552 KB
#include <bits/stdc++.h>
#include <chrono>
#include <math.h>
#pragma GCC optimize("-O3")
using namespace std;
#define endl "\n"
#define mp make_pair
#define st first
#define nd second
#define pii pair<int, int>
#define pb push_back
#define _upgrade ios_base::sync_with_stdio(0), cout.setf(ios::fixed), cout.precision(10), cin.tie(0), cout.tie(0);
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define FWD(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define fwd(i, a, b) for (int i = (a); i < (b); ++i)
#define all(c) (c).begin(), (c).end()
#define sz(X) (int)((X).size())
#ifdef LOCAL
ostream &operator<<(ostream &out, string str) {
   for (char c : str)
      out << c;
   return out;
}
template <class L, class R> ostream &operator<<(ostream &out, pair<L, R> p) { return out << "(" << p.st << ", " << p.nd << ")"; }
template <class T> auto operator<<(ostream &out, T a) -> decltype(a.begin(), out) {
   out << '{';
   for (auto it = a.begin(); it != a.end(); it = next(it))
      out << (it != a.begin() ? ", " : "") << *it;
   return out << '}';
}
void dump() { cerr << "\n"; }
template <class T, class... Ts> void dump(T a, Ts... x) {
   cerr << a << ", ";
   dump(x...);
}
#define debug(...) cerr << "[" #__VA_ARGS__ "]: ", dump(__VA_ARGS__)
#else
#define debug(...)                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     \
   {}
#endif

const int MAXN = 205;
const int MOD = 1e9 + 7;

long long tab[MAXN][MAXN][MAXN];

inline int change(int &AB, int &BC, int &CA, int stan) {
   if ((AB + CA) == 0)
      return stan;

   if (stan == 0) {
      if (AB == 0)
         return 0;
      AB--;
      return AB + 1;
   }
   if (stan == 1) {
      if (CA == 0)
         return 0;
      CA--;
      BC++;
      return CA + 1;
   }
}

vector<pair<pii, int>> S[3 * MAXN];

int32_t main() {
   _upgrade;
   int N, T;
   cin >> N >> T;

   tab[0][0][0] = 1;

   rep(i, 2 * N + 1) rep(j, 2 * N + 1) rep(k, 2 * N + 1) if (i + j + k <= 3 * N) S[i + j + k].push_back({{i, j}, k});
   for (int s = 1; s < 3 * MAXN; s++)
      for (auto v : S[s]) {

         int i = v.st.st;
         int j = v.st.nd;
         int k = v.nd;

         for (int l = 0; l < 8; l++) {
            int mnoznik = 1;
            int AB = i;
            int BC = j;
            int CA = k;
            int ll = l;

            mnoznik *= change(AB, BC, CA, ll % 2);
            ll /= 2;

            mnoznik *= change(BC, CA, AB, ll % 2);
            ll /= 2;

            mnoznik *= change(CA, AB, BC, ll % 2);
            ll /= 2;

            if (AB + BC + CA != i + j + k && mnoznik != 0) {
               if (AB >= MAXN || BC >= MAXN || CA >= MAXN) {
                  debug(AB, BC, CA, i, j, k, mnoznik, l);
                  exit(1);
               }
               if (i == 0 && j == 1 && k == 1)
                  debug(i, j, k, AB, BC, CA, mnoznik, l);
               tab[i][j][k] = (tab[i][j][k] + tab[AB][BC][CA] * mnoznik) % MOD;
            }
         }
      }

   rep(i, 5) rep(j, 5) rep(k, 5) debug(i, j, k, tab[i][j][k]);

   while (T--) {
      set<int> S[3];
      int AB = 0;
      int BC = 0;
      int CA = 0;
      rep(i, 3) rep(j, 2 * N) {
         int a;
         cin >> a;
         --a;
         S[i].insert(a);
      }
      debug(S[0], S[1], S[2]);
      rep(i, 3 * N) {
         if (S[0].count(i) && S[1].count(i))
            AB++;
         if (S[2].count(i) && S[1].count(i))
            BC++;
         if (S[2].count(i) && S[0].count(i))
            CA++;
      }
      debug(AB, BC, CA);
      cout << tab[AB][BC][CA] << endl;
   }
}

Compilation message

fishing.cpp: In function 'int change(int&, int&, int&, int)':
fishing.cpp:65:1: warning: control reaches end of non-void function [-Wreturn-type]
   65 | }
      | ^
# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 2 ms 1132 KB Output is correct
4 Correct 6 ms 3564 KB Output is correct
5 Correct 76 ms 23436 KB Output is correct
6 Correct 129 ms 37236 KB Output is correct
7 Correct 205 ms 51308 KB Output is correct
8 Correct 312 ms 72224 KB Output is correct
9 Correct 484 ms 91840 KB Output is correct
10 Correct 681 ms 114552 KB Output is correct