Submission #199032

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
199032	2020-01-28T17:18:49 Z	popovicirobert	Fishing Game (RMI19_fishing)	C++14	100 / 100	828 ms	32248 KB

fishing

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define uint unsigned int


using namespace std;

template <typename T, T MOD>
class ModInt;

template <typename T, T MOD>
ModInt<T, MOD> lgpow(ModInt<T, MOD> a, ll b) {
    assert(b >= 0);

    ModInt<T, MOD> ans(1);
    while(b > 0) {
        if(b & 1) ans *= a;
        b >>= 1, a *= a;
    }
    return ans;
}

template <typename T, T MOD>
ModInt<T, MOD> inv(ModInt<T, MOD> a) {
    return lgpow(a, MOD - 2);
}


template <typename T, T MOD>
class ModInt {

protected:

    T val;

    inline T mod(ll x) const {
        if(llabs(x) >= MOD) {
            x %= MOD;
        }
        return (x < 0 ? MOD : 0) + x;
    }

public:

    explicit ModInt(ll _val = 0) : val(mod(_val)) {}
    ModInt(const ModInt &y) : val(y.val) {}

    ModInt operator +(const ModInt &y) const {
        return ModInt(mod(val + y.val));
    }
    ModInt operator +(const ll &y) const {
        return *this + ModInt(y);
    }
    ModInt operator -(const ModInt &y) const {
        return ModInt(mod(val - y.val));
    }
    ModInt operator -(const ll &y) const {
        return *this - ModInt(y);
    }
    ModInt operator *(const ModInt &y) const {
        return ModInt(mod(1LL * val * y.val));
    }
    ModInt operator *(const ll &y) const {
        return *this * ModInt(y);
    }
    ModInt operator /(const ModInt &y) const {
        return ModInt(mod(1LL * val * inv(y).val));
    }
    ModInt operator /(const ll &y) const {
        return *this / ModInt(y);
    }
    ModInt& operator =(const ModInt &y) {
        val = y.val;
        return *this;
    }
    ModInt& operator =(const ll &y) {
        val = mod(y);
        return *this;
    }

    bool operator ==(const ModInt &y) const {
        return val == y.val;
    }
    bool operator ==(const T &y) const {
        return val == y;
    }
    bool operator !=(const ModInt &y) const {
        return val != y.val;
    }
    bool operator !=(const T &y) const {
        return val != y;
    }
    bool operator <(const ModInt &y) const {
        return val < y.val;
    }
    bool operator <(const T &y) const {
        return val < y;
    }
    bool operator <=(const ModInt &y) const {
        return val <= y.val;
    }
    bool operator <=(const T &y) const {
        return val <= y;
    }
    bool operator >(const ModInt &y) const {
        return val > y.val;
    }
    bool operator >(const T &y) const {
        return val > y;
    }
    bool operator >=(const ModInt &y) const {
        return val >= y.val;
    }
    bool operator >=(const T &y) const {
        return val >= y;
    }

    ModInt& operator +=(const ModInt &y) {
        val = mod(val + y.val);
        return *this;
    }
    ModInt& operator +=(const T &y) {
        val = mod(val + y);
        return *this;
    }
    ModInt& operator -=(const ModInt &y) {
        val = mod(val - y.val);
        return *this;
    }
    ModInt& operator -=(const T &y) {
        val = mod(val - y);
        return *this;
    }
    ModInt& operator *=(const ModInt &y) {
        val = mod(1LL * val * y.val);
        return *this;
    }
    ModInt& operator *=(const T &y) {
        val = mod(1LL * val * y);
        return *this;
    }
    ModInt& operator /=(const ModInt &y) {
        val = mod(1LL * val * inv(y.val));
        return *this;
    }
    ModInt& operator /=(const T &y) {
        val = mod(1LL * val * inv(y));
        return *this;
    }

    ModInt& operator ++() {
        val = mod(val + 1);
        return *this;
    }
    ModInt operator ++(int) {
        ModInt ans(val);
        val = mod(val + 1);
        return ans;
    }
    ModInt& operator --() {
        val = mod(val - 1);
        return *this;
    }
    ModInt operator --(int) {
        ModInt ans(val);
        val = mod(val - 1);
        return ans;
    }

    operator int() const {
        return (int)val;
    }
    operator ll() const {
        return (ll)val;
    }


    friend std::ostream& operator <<(std::ostream &stream, const ModInt &x) {
        return stream << x.val;
    }
    friend std::istream& operator >>(std::istream &stream, ModInt &x) {
        ll cur;
        stream >> cur;
        x = ModInt<T, MOD>(cur);
        return stream;
    }

    friend ModInt operator +(ll x, const ModInt &y) {
        return ModInt(x) + y;
    }
    friend ModInt operator -(ll x, const ModInt &y) {
        return ModInt(x) - y;
    }
    friend ModInt operator *(ll x, const ModInt &y) {
        return ModInt(x) * y;
    }
    friend ModInt operator /(ll x, const ModInt &y) {
        return ModInt(x) / y;
    }
    friend ModInt operator +=(ll x, const ModInt &y) {
        return ModInt(x) + y;
    }
    friend ModInt operator -=(ll x, const ModInt &y) {
        return ModInt(x) - y;
    }
    friend ModInt operator *=(ll x, const ModInt &y) {
        return ModInt(x) * y;
    }
    friend ModInt operator /=(ll x, const ModInt &y) {
        return ModInt(x) / y;
    }

};


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

using Mint = ModInt<int, MOD>;

const int MAXN = 200;

Mint dp[MAXN + 1][MAXN + 1][MAXN + 1];

void bkt(int a, int b, int c, bool ok, int id, Mint prd) {
    if(a < 0 || b < 0 || c < 0 || prd == 0) return ;
    if(id == 3) {
        dp[a][b][c] += prd * ok;
        return ;
    }
    else {
        int sza = a + c, szb = a + b, szc = b + c;
        //cerr << a << " " << b << " " << c << " " << id << "\n";
        if(id == 0) {
            if(sza == 0) {
                bkt(a, b, c, ok, id + 1, prd);
            }
            else {
                bkt(a, b + 1, c - 1, ok, id + 1, prd * (sza - a));
                bkt(a - 1, b, c, ok | 1, id + 1, prd * a);
            }
        }
        if(id == 1) {
            if(szb == 0) {
                bkt(a, b, c, ok, id + 1, prd);
            }
            else {
                bkt(a - 1, b, c + 1, ok, id + 1, prd * (szb - b));
                bkt(a, b - 1, c, ok | 1, id + 1, prd * b);
            }
        }
        if(id == 2) {
            if(szc == 0) {
                bkt(a, b, c, ok, id + 1, prd);
            }
            else {
                bkt(a + 1, b - 1, c, ok, id + 1, prd * (szc - c));
                bkt(a, b, c - 1, ok | 1, id + 1, prd * c);
            }
        }
    }
}

int main() {
#ifdef HOME
    ifstream cin("A.in");
    ofstream cout("A.out");
#endif
    int i, j, n, t;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> t;

    while(t--) {
        vector < vector <int> > fr(3, vector <int>(3 * n));
        for(j = 0; j < 3; j++) {
            for(i = 0; i < 2 * n; i++) {
                int x;
                cin >> x;
                x--;
                fr[j][x]++;
            }
        }

        vector <int> comm(3);
        for(j = 0; j < 3; j++) {
            for(i = 0; i < 3 * n; i++) {
                comm[j] += (fr[j][i] & fr[(j + 1) % 3][i]);
            }
        }

        for(int a = 0; a <= 2 * n; a++) {
            for(int b = 0; b <= 2 * n; b++) {
                for(int c = 0; c <= 2 * n; c++) {
                    dp[a][b][c] = 0;
                }
            }
        }

        dp[comm[0]][comm[1]][comm[2]] = 1;

        for(int sum = comm[0] + comm[1] + comm[2]; sum > 0; sum--) {
            for(int a = 0; a <= 2 * n; a++) {
                for(int b = 0; b <= 2 * n; b++) {
                    int c = sum - a - b;
                    if(c < 0 || c > 2 * n || dp[a][b][c] == 0) continue;

                    bkt(a, b, c, 0, 0, dp[a][b][c]);
                }
            }
        }

        cout << dp[0][0][0] << "\n";
    }

    return 0;
}

Compilation message

fishing.cpp: In function 'void bkt(int, int, int, bool, int, Mint)':
fishing.cpp:229:30: warning: ISO C++ says that these are ambiguous, even though the worst conversion for the first is better than the worst conversion for the second:
         dp[a][b][c] += prd * ok;
                              ^~
fishing.cpp:65:12: note: candidate 1: ModInt<T, MOD> ModInt<T, MOD>::operator*(const long long int&) const [with T = int; T MOD = 1000000007]
     ModInt operator *(const ll &y) const {
            ^~~~~~~~
fishing.cpp:229:30: note: candidate 2: operator*(long long int, int) <built-in>
         dp[a][b][c] += prd * ok;
                              ^~
fishing.cpp:229:30: warning: ISO C++ says that these are ambiguous, even though the worst conversion for the first is better than the worst conversion for the second:
fishing.cpp:65:12: note: candidate 1: ModInt<T, MOD> ModInt<T, MOD>::operator*(const long long int&) const [with T = int; T MOD = 1000000007]
     ModInt operator *(const ll &y) const {
            ^~~~~~~~
fishing.cpp:229:30: note: candidate 2: operator*(int, int) <built-in>
         dp[a][b][c] += prd * ok;
                              ^~
fishing.cpp:240:64: warning: ISO C++ says that these are ambiguous, even though the worst conversion for the first is better than the worst conversion for the second:
                 bkt(a, b + 1, c - 1, ok, id + 1, prd * (sza - a));
                                                                ^
fishing.cpp:65:12: note: candidate 1: ModInt<T, MOD> ModInt<T, MOD>::operator*(const long long int&) const [with T = int; T MOD = 1000000007]
     ModInt operator *(const ll &y) const {
            ^~~~~~~~
fishing.cpp:240:64: note: candidate 2: operator*(long long int, int) <built-in>
                 bkt(a, b + 1, c - 1, ok, id + 1, prd * (sza - a));
                                                                ^
fishing.cpp:240:64: warning: ISO C++ says that these are ambiguous, even though the worst conversion for the first is better than the worst conversion for the second:
fishing.cpp:65:12: note: candidate 1: ModInt<T, MOD> ModInt<T, MOD>::operator*(const long long int&) const [with T = int; T MOD = 1000000007]
     ModInt operator *(const ll &y) const {
            ^~~~~~~~
fishing.cpp:240:64: note: candidate 2: operator*(int, int) <built-in>
                 bkt(a, b + 1, c - 1, ok, id + 1, prd * (sza - a));
                                                                ^
fishing.cpp:241:56: warning: ISO C++ says that these are ambiguous, even though the worst conversion for the first is better than the worst conversion for the second:
                 bkt(a - 1, b, c, ok | 1, id + 1, prd * a);
                                                        ^
fishing.cpp:65:12: note: candidate 1: ModInt<T, MOD> ModInt<T, MOD>::operator*(const long long int&) const [with T = int; T MOD = 1000000007]
     ModInt operator *(const ll &y) const {
            ^~~~~~~~
fishing.cpp:241:56: note: candidate 2: operator*(long long int, int) <built-in>
                 bkt(a - 1, b, c, ok | 1, id + 1, prd * a);
                                                        ^
fishing.cpp:241:56: warning: ISO C++ says that these are ambiguous, even though the worst conversion for the first is better than the worst conversion for the second:
fishing.cpp:65:12: note: candidate 1: ModInt<T, MOD> ModInt<T, MOD>::operator*(const long long int&) const [with T = int; T MOD = 1000000007]
     ModInt operator *(const ll &y) const {
            ^~~~~~~~
fishing.cpp:241:56: note: candidate 2: operator*(int, int) <built-in>
                 bkt(a - 1, b, c, ok | 1, id + 1, prd * a);
                                                        ^
fishing.cpp:249:64: warning: ISO C++ says that these are ambiguous, even though the worst conversion for the first is better than the worst conversion for the second:
                 bkt(a - 1, b, c + 1, ok, id + 1, prd * (szb - b));
                                                                ^
fishing.cpp:65:12: note: candidate 1: ModInt<T, MOD> ModInt<T, MOD>::operator*(const long long int&) const [with T = int; T MOD = 1000000007]
     ModInt operator *(const ll &y) const {
            ^~~~~~~~
fishing.cpp:249:64: note: candidate 2: operator*(long long int, int) <built-in>
                 bkt(a - 1, b, c + 1, ok, id + 1, prd * (szb - b));
                                                                ^
fishing.cpp:249:64: warning: ISO C++ says that these are ambiguous, even though the worst conversion for the first is better than the worst conversion for the second:
fishing.cpp:65:12: note: candidate 1: ModInt<T, MOD> ModInt<T, MOD>::operator*(const long long int&) const [with T = int; T MOD = 1000000007]
     ModInt operator *(const ll &y) const {
            ^~~~~~~~
fishing.cpp:249:64: note: candidate 2: operator*(int, int) <built-in>
                 bkt(a - 1, b, c + 1, ok, id + 1, prd * (szb - b));
                                                                ^
fishing.cpp:250:56: warning: ISO C++ says that these are ambiguous, even though the worst conversion for the first is better than the worst conversion for the second:
                 bkt(a, b - 1, c, ok | 1, id + 1, prd * b);
                                                        ^
fishing.cpp:65:12: note: candidate 1: ModInt<T, MOD> ModInt<T, MOD>::operator*(const long long int&) const [with T = int; T MOD = 1000000007]
     ModInt operator *(const ll &y) const {
            ^~~~~~~~
fishing.cpp:250:56: note: candidate 2: operator*(long long int, int) <built-in>
                 bkt(a, b - 1, c, ok | 1, id + 1, prd * b);
                                                        ^
fishing.cpp:250:56: warning: ISO C++ says that these are ambiguous, even though the worst conversion for the first is better than the worst conversion for the second:
fishing.cpp:65:12: note: candidate 1: ModInt<T, MOD> ModInt<T, MOD>::operator*(const long long int&) const [with T = int; T MOD = 1000000007]
     ModInt operator *(const ll &y) const {
            ^~~~~~~~
fishing.cpp:250:56: note: candidate 2: operator*(int, int) <built-in>
                 bkt(a, b - 1, c, ok | 1, id + 1, prd * b);
                                                        ^
fishing.cpp:258:64: warning: ISO C++ says that these are ambiguous, even though the worst conversion for the first is better than the worst conversion for the second:
                 bkt(a + 1, b - 1, c, ok, id + 1, prd * (szc - c));
                                                                ^
fishing.cpp:65:12: note: candidate 1: ModInt<T, MOD> ModInt<T, MOD>::operator*(const long long int&) const [with T = int; T MOD = 1000000007]
     ModInt operator *(const ll &y) const {
            ^~~~~~~~
fishing.cpp:258:64: note: candidate 2: operator*(long long int, int) <built-in>
                 bkt(a + 1, b - 1, c, ok, id + 1, prd * (szc - c));
                                                                ^
fishing.cpp:258:64: warning: ISO C++ says that these are ambiguous, even though the worst conversion for the first is better than the worst conversion for the second:
fishing.cpp:65:12: note: candidate 1: ModInt<T, MOD> ModInt<T, MOD>::operator*(const long long int&) const [with T = int; T MOD = 1000000007]
     ModInt operator *(const ll &y) const {
            ^~~~~~~~
fishing.cpp:258:64: note: candidate 2: operator*(int, int) <built-in>
                 bkt(a + 1, b - 1, c, ok, id + 1, prd * (szc - c));
                                                                ^
fishing.cpp:259:56: warning: ISO C++ says that these are ambiguous, even though the worst conversion for the first is better than the worst conversion for the second:
                 bkt(a, b, c - 1, ok | 1, id + 1, prd * c);
                                                        ^
fishing.cpp:65:12: note: candidate 1: ModInt<T, MOD> ModInt<T, MOD>::operator*(const long long int&) const [with T = int; T MOD = 1000000007]
     ModInt operator *(const ll &y) const {
            ^~~~~~~~
fishing.cpp:259:56: note: candidate 2: operator*(long long int, int) <built-in>
                 bkt(a, b, c - 1, ok | 1, id + 1, prd * c);
                                                        ^
fishing.cpp:259:56: warning: ISO C++ says that these are ambiguous, even though the worst conversion for the first is better than the worst conversion for the second:
fishing.cpp:65:12: note: candidate 1: ModInt<T, MOD> ModInt<T, MOD>::operator*(const long long int&) const [with T = int; T MOD = 1000000007]
     ModInt operator *(const ll &y) const {
            ^~~~~~~~
fishing.cpp:259:56: note: candidate 2: operator*(int, int) <built-in>
                 bkt(a, b, c - 1, ok | 1, id + 1, prd * c);
                                                        ^

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	32120 KB	Output is correct
2	Correct	23 ms	32120 KB	Output is correct
3	Correct	24 ms	32120 KB	Output is correct
4	Correct	27 ms	32120 KB	Output is correct
5	Correct	124 ms	32248 KB	Output is correct
6	Correct	202 ms	32120 KB	Output is correct
7	Correct	307 ms	32248 KB	Output is correct
8	Correct	448 ms	32248 KB	Output is correct
9	Correct	598 ms	32120 KB	Output is correct
10	Correct	828 ms	32172 KB	Output is correct