Submission #526279

#	Time	Username	Problem	Language	Result	Execution time	Memory
526279		Jeff12345121	Kangaroo (CEOI16_kangaroo)	C++14	0 / 100	1 ms	296 KiB

kangaroo

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

#ifdef LOCAL
ifstream in("in.in");
ofstream out("out.out");
#else
#define in cin
#define out cout
#endif

const int nmax = 205;
int n,cs,cf,dp[nmax][nmax][nmax][2];///third means on which position from left to right is the cf, NOT CONSIDERING
///current one
struct wow {
    int l,r,pos,dir;
};
queue<wow> q;
int ans = 0;
void extend(int l, int r,int pos, int dir) {
    int low,high;
    if (dir == 0) {
        low = 0; /// how many there are left of this guy
        high = l - 1; /// same
    } else {
        low = l;
        high = l + r - 1;
    }
    for (int newLeft = low; newLeft <= high; newLeft++) {
        int newRight = l + r - newLeft - 1;
        int newPos;
        if (newLeft + 1 < pos) {/// this is left of the target
            newPos = pos - 1;
        } else if (newLeft + 1 == pos){
            ans += dp[l][r][pos][dir];
            continue;
        } else {
            newPos = pos;
        }
        int newDir = 1 - dir;
        dp[newLeft][newRight][newPos][newDir] += dp[l][r][newPos][dir];
        q.push({newLeft, newRight , newPos, newDir});
    }
}
int main() {
    in >> n >> cs >> cf;
    //dp is all 0 init, dp[st][dr][dir you will go now 0 = st, 1 = dr] = number of ways to get here
    int l,r,pos;
    if (cs <= cf) {
        l = cs - 1;
        r = n - cs;
        pos = cf - 1;
    } else {
        l = cs - 1;
        r = n - cs;
        pos = cf;
    }

    dp[l][r][pos][0] = dp[l][r][pos][1] = 1;
    q.push({l, r, pos,0});
    q.push({l, r, pos,1});
    ans = 0;
    while(!q.empty()) {
        int l = q.front().l;
        int r = q.front().r;
        int pos = q.front().pos;
        int dir = q.front().dir;
        q.pop();
        extend(l,r,pos,dir);
    }

    out << ans << "\n";


}

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