Submission #1117653

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117653		nasir_bashirov	Kangaroo (CEOI16_kangaroo)	C++11	6 / 100	2021 ms	336 KiB

kangaroo

// #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;
    // }
}

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