oj.uz

Submission #44780

# Submission time Handle Problem Language Result Execution time Memory
44780 2018-04-06T11:03:37 Z bogdan10bos Kangaroo (CEOI16_kangaroo) C++14
51 / 100
 499 ms 32232 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[205][205][205][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 248 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 248 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 3 ms 972 KB Output is correct
4 Correct 4 ms 1452 KB Output is correct
5 Correct 3 ms 1816 KB Output is correct
6 Correct 3 ms 1816 KB Output is correct
7 Correct 3 ms 1816 KB Output is correct
8 Correct 3 ms 1848 KB Output is correct
9 Correct 3 ms 1848 KB Output is correct
10 Correct 3 ms 1848 KB Output is correct
11 Correct 3 ms 1848 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 3 ms 972 KB Output is correct
4 Correct 4 ms 1452 KB Output is correct
5 Correct 3 ms 1816 KB Output is correct
6 Correct 3 ms 1816 KB Output is correct
7 Correct 3 ms 1816 KB Output is correct
8 Correct 3 ms 1848 KB Output is correct
9 Correct 3 ms 1848 KB Output is correct
10 Correct 3 ms 1848 KB Output is correct
11 Correct 3 ms 1848 KB Output is correct
12 Correct 477 ms 14840 KB Output is correct
13 Correct 321 ms 18956 KB Output is correct
14 Correct 50 ms 32232 KB Output is correct
15 Correct 499 ms 32232 KB Output is correct
16 Correct 70 ms 32232 KB Output is correct
17 Correct 477 ms 32232 KB Output is correct
18 Correct 151 ms 32232 KB Output is correct
19 Correct 466 ms 32232 KB Output is correct
20 Correct 461 ms 32232 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 3 ms 972 KB Output is correct
4 Correct 4 ms 1452 KB Output is correct
5 Correct 3 ms 1816 KB Output is correct
6 Correct 3 ms 1816 KB Output is correct
7 Correct 3 ms 1816 KB Output is correct
8 Correct 3 ms 1848 KB Output is correct
9 Correct 3 ms 1848 KB Output is correct
10 Correct 3 ms 1848 KB Output is correct
11 Correct 3 ms 1848 KB Output is correct
12 Correct 477 ms 14840 KB Output is correct
13 Correct 321 ms 18956 KB Output is correct
14 Correct 50 ms 32232 KB Output is correct
15 Correct 499 ms 32232 KB Output is correct
16 Correct 70 ms 32232 KB Output is correct
17 Correct 477 ms 32232 KB Output is correct
18 Correct 151 ms 32232 KB Output is correct
19 Correct 466 ms 32232 KB Output is correct
20 Correct 461 ms 32232 KB Output is correct
21 Runtime error 8 ms 32232 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -