Submission #1117748

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117748		vjudge1	Kangaroo (CEOI16_kangaroo)	C++17	6 / 100	2062 ms	1096 KiB

kangaroo

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int mod = 1e9 + 7;

int32_t main () {

    ios_base::sync_with_stdio(0); 
    cin.tie(0); 
    cout.tie(0); 

    int N, U, V;
    cin >> N >> U >> V;
    -- U;
    -- V;
    map<long long, int> memo;
    function<int(long long, int, int )> func = [&](long long tmp, int ind, int dir) -> int {
        if (ind == V) {
            memo[tmp] = (tmp == 0);
            return (tmp == 0);
        }
        bool ch = (memo.find(tmp) == memo.end());
        int ans = 0;
        if (dir != 0) {
            bool as = false;
            for (int i = ind + 1;i < N;i ++) if ((tmp & (1LL << i)) > 0) {
                as = true;
                break;
            }
            if (!as) {
                if (memo.find(tmp) == memo.end()) memo[tmp] = 0;
            } else {
                for (int i = ind + 1;i < N;i ++) if ((tmp & (1LL << i)) > 0) {
                    ans = (ans + func ((tmp ^ (1LL << i)), i, 0)) % mod;
                    // memo[tmp] = (memo[(tmp ^ (1LL << i))] + memo[tmp]) % mod;
                }
            }
        }
        if (dir != 1) {
            bool as = false;
            for (int i = ind - 1;i >= 0;i --) if ((tmp & (1LL << i)) > 0) {
                as = true;
                break;
            }
            if (!as) {
                if (memo.find(tmp) == memo.end()) memo[tmp] = 0;
            } else {
                for (int i = ind - 1;i >= 0;i --) if ((tmp & (1LL << i)) > 0) {
                    ans = (ans + func ((tmp ^ (1LL << i)), i, 1));
                    // memo[tmp] = (memo[(tmp ^ (1LL << i))] + memo[tmp]) % mod;
                }
            }
        }
        memo[tmp] = (memo[tmp] + ans) % mod;
        return ans;
    };
    func (((1LL << N) - 1) ^ (1LL<< U), U, -1);

    // cout << (((1 << N) - 1) ^ (1 << U)) << "\n";
    cout << memo[((1LL << N) - 1) ^ (1LL << U)] << "\n";
    // for (auto v : memo) {
    //     cout << v.first << " " << v.second << "\n";
    // }
}

Compilation message (stderr)

kangaroo.cpp: In lambda function:
kangaroo.cpp:24:14: warning: unused variable 'ch' [-Wunused-variable]
   24 |         bool ch = (memo.find(tmp) == memo.end());
      |              ^~

• Subtask 1: 6 / 6
• Subtask 2: 0 / 30
• Subtask 3: 0 / 15
• Subtask 4: 0 / 49