Submission #1117863

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117863		vjudge1	Kangaroo (CEOI16_kangaroo)	C++17	6 / 100	1 ms	336 KiB

kangaroo

#pragma GCC optimize ("O3")
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define vl vector<ll>
#define vi vector<int>
#define all(v) v.begin(), v.end()
#define pb push_back
#define iospeed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
int main()
{
    iospeed
    ll n, cs, cf, i;
    cin >> n >> cs >> cf;
    if(n <= 8){
        vl v;
        for(i = 1; i <= n; i++)
            v.pb(i);
        ll res = 0;
        do{
            if(v[0] != cs || v.back() != cf)
                continue;
            ll lst = 1;
            if(v[1] < v[0])
                lst = 0;
            bool ok = true;
            for(i = 2; i < n; i++)
            {
                if((v[i] > v[i-1] && lst) || (v[i] < v[i-1] && !lst)){
                    ok = false;
                    break;
                }
                lst = 1 - lst;
            }
            if(ok)
                res++;
        }while(next_permutation(all(v)));
        cout << res << "\n";
    }
    else    if(n % 2)
    {
        if(cs > cf)
            swap(cs, cf);
        if(n == 3)
        {
            if((cs == 1 && cf == 2) || (cs == 2 && cf == 3))
                cout << 1 << endl;
            else
                cout << 0 << endl;
        }
        else
        {
            vl init;
            init.pb(0);
            init.pb(1);
            init.pb(0);
            int now = 3;
            while(now != n)
            {
                now += 2;
                vl pref;
                ll g = 0;
                for(auto u : init){
                    g += u;
                    pref.pb(g);
                }
                reverse(all(pref));
                vl tmp;
                tmp.pb(0);
                g = 0;
                for(auto u : pref)
                {
                    g += u;
                    tmp.pb(g);
                }
                tmp.pb(0);
                reverse(all(tmp));
                init = tmp;
            }
            cf -= cs;
            cout << init[cf] << endl;
        }
    }
}

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