Submission #44781

#	Time	Username	Problem	Language	Result	Execution time	Memory
44781		bogdan10bos	Kangaroo (CEOI16_kangaroo)	C++14	51 / 100	516 ms	62308 KiB

kangaroo

#include <bits/stdc++.h>

using namespace std;

//#define FILE_IO

const int mod = 1e9 + 7;

struct state
{
    int st, mid, dr;
    bool dir;
};

bool operator< (const state &a, const state &b)
{
    return a.st < b.st;
}

int mp[405][405][405][2];
queue<state> q;

int main()
{
    #ifdef FILE_IO
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
    #endif

    int N, st, fn;
    scanf("%d%d%d", &N, &st, &fn);

    state start;
    if(st <= fn)
    {
        start.st = st - 1;
        start.mid = fn - st - 1;
        start.dr = N - fn;
    }
    else
    {
        start.st = N - st;
        start.mid = st - fn - 1;
        start.dr = fn - 1;
    }

    start.dir = 0;
    mp[start.st][start.mid][start.dr][start.dir] = 1;
    q.push(start);

    start.dir = 1;
    mp[start.st][start.mid][start.dr][start.dir] = 1;
    q.push(start);

    int ans = 0;
    while(!q.empty())
    {
        state s = q.front();
        q.pop();
        int val = mp[s.st][s.mid][s.dr][s.dir];

        if(s.st == 0 && s.mid == 0 && s.dr == 0 && s.dir == 1)
        {
            (ans += val) %= mod;
            continue;
        }

        if(s.dir == 0)
        {
            for(int i = 1; i <= s.st; i++)
            {
                state newS = s;
                int newst = s.st - i;
                int newmid = s.mid + i - 1;
                newS.st = newst;
                newS.mid = newmid;
                newS.dir = 1;

                if(!mp[newS.st][newS.mid][newS.dr][newS.dir]) q.push(newS);
                (mp[newS.st][newS.mid][newS.dr][newS.dir] += val) %= mod;
            }
        }
        else
        {
            for(int i = 1; i <= s.mid; i++)
            {
                state newS = s;
                int newst = s.st + i - 1;
                int newmid = s.mid - i;
                newS.st = newst;
                newS.mid = newmid;
                newS.dir = 0;

                if(!mp[newS.st][newS.mid][newS.dr][newS.dir]) q.push(newS);
                (mp[newS.st][newS.mid][newS.dr][newS.dir] += val) %= mod;
            }

            for(int i = 1; i <= s.dr; i++)
            {
                state newS = s;
                int newdr = s.st + s.mid;
                int newmid = i - 1;
                int newst = s.dr - i;
                newS.st = newst;
                newS.mid = newmid;
                newS.dr = newdr;
                newS.dir = 1;

                if(!mp[newS.st][newS.mid][newS.dr][newS.dir]) q.push(newS);
                (mp[newS.st][newS.mid][newS.dr][newS.dir] += val) %= mod;
            }
        }
    }
    printf("%d\n", ans);

    return 0;
}

Compilation message (stderr)

kangaroo.cpp: In function 'int main()':
kangaroo.cpp:31:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &N, &st, &fn);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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