oj.uz

Submission #44781

# Submission time Handle Problem Language Result Execution time Memory
44781 2018-04-06T11:04:34 Z bogdan10bos Kangaroo (CEOI16_kangaroo) C++14
51 / 100
 516 ms 62308 KB 
#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

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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 3 ms 1460 KB Output is correct
4 Correct 4 ms 2096 KB Output is correct
5 Correct 4 ms 2772 KB Output is correct
6 Correct 4 ms 2772 KB Output is correct
7 Correct 3 ms 2772 KB Output is correct
8 Correct 4 ms 2772 KB Output is correct
9 Correct 4 ms 2772 KB Output is correct
10 Correct 4 ms 2772 KB Output is correct
11 Correct 4 ms 2772 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 3 ms 1460 KB Output is correct
4 Correct 4 ms 2096 KB Output is correct
5 Correct 4 ms 2772 KB Output is correct
6 Correct 4 ms 2772 KB Output is correct
7 Correct 3 ms 2772 KB Output is correct
8 Correct 4 ms 2772 KB Output is correct
9 Correct 4 ms 2772 KB Output is correct
10 Correct 4 ms 2772 KB Output is correct
11 Correct 4 ms 2772 KB Output is correct
12 Correct 516 ms 27576 KB Output is correct
13 Correct 348 ms 35624 KB Output is correct
14 Correct 83 ms 62308 KB Output is correct
15 Correct 493 ms 62308 KB Output is correct
16 Correct 133 ms 62308 KB Output is correct
17 Correct 496 ms 62308 KB Output is correct
18 Correct 197 ms 62308 KB Output is correct
19 Correct 457 ms 62308 KB Output is correct
20 Correct 484 ms 62308 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 3 ms 1460 KB Output is correct
4 Correct 4 ms 2096 KB Output is correct
5 Correct 4 ms 2772 KB Output is correct
6 Correct 4 ms 2772 KB Output is correct
7 Correct 3 ms 2772 KB Output is correct
8 Correct 4 ms 2772 KB Output is correct
9 Correct 4 ms 2772 KB Output is correct
10 Correct 4 ms 2772 KB Output is correct
11 Correct 4 ms 2772 KB Output is correct
12 Correct 516 ms 27576 KB Output is correct
13 Correct 348 ms 35624 KB Output is correct
14 Correct 83 ms 62308 KB Output is correct
15 Correct 493 ms 62308 KB Output is correct
16 Correct 133 ms 62308 KB Output is correct
17 Correct 496 ms 62308 KB Output is correct
18 Correct 197 ms 62308 KB Output is correct
19 Correct 457 ms 62308 KB Output is correct
20 Correct 484 ms 62308 KB Output is correct
21 Runtime error 25 ms 62308 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -