Submission #1117666

#TimeUsernameProblemLanguageResultExecution timeMemory
1117666vjudge1Kangaroo (CEOI16_kangaroo)C++17
6 / 100
2054 ms508 KiB
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
 
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define db long double
#define vll vector<pll>
#define endl '\n'
#define all(x) x.begin(), x.end()
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
#define int long long
 
int res = 0, n, a, b;
vi path;
 
void dfs(int node, int cnt, int pre, vector<bool> used){
    if(cnt == n - 1 and node == b){
        res++;
        // for(int i : path){
        //     cout << i << " ";
        // }
        // cout << endl;
        return;
    }
    if(cnt == n - 1)    return;
    if(pre != 1){
        for(int i = node + 1; i <= n; i++){
            if(used[i]) continue;
            path.push_back(i);
            used[i] = true;
            dfs(i, cnt + 1, 1, used);
            path.pop_back();
            used[i] = false;
        }
    }
    if(pre != 0){
        for(int i = node - 1; i >= 1; i--){
            if(used[i]) continue;
            path.push_back(i);
            used[i] = true;
            dfs(i, cnt + 1, 0, used);
            path.pop_back();
            used[i] = false;
        }
    }
}
 
void fmain(){
    cin >> n >> a >> b;
    vector<bool> usd(n + 1, false);
    path.push_back(a);
    usd[a] = true;
    dfs(a, 0, -1, usd);
    cout << res << " ";
    path.clear();
}
 
signed main(){
    int tmr = 1;
    // cin >> tmr;
    while(tmr--){
        fmain();
    }
    // n = 6;
    // for(int i = 1; i <= n; i++){
    //     for(int j = 1; j <= n; j++){
    //         if(i == j){
    //             cout << 0 << " ";
    //             continue;
    //         }
    //         a = i, b = j;
    //         fmain();
    //     }
    //     cout << endl;
    // }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...