Submission details
Task:Grid Paths II
Sender:niketin
Submission time:2020-09-19 23:54:21 +0300
Language:C++ (C++17)
Status:READY
Result:
Test results
testverdicttime
#10.01 sdetails
#20.01 sdetails
#30.01 sdetails
#40.01 sdetails
#50.01 sdetails
#60.01 sdetails
#70.01 sdetails
#80.01 sdetails
#90.01 sdetails
#100.01 sdetails

Compiler report

input/code.cpp: In function 'bool is_trap_fi(llu, llu)':
input/code.cpp:21:13: warning: unused variable 'u' [-Wunused-variable]
         int u = 0;
             ^
input/code.cpp: In function 'bool is_trap_se(llu, llu, llu)':
input/code.cpp:31:13: warning: unused variable 'u' [-Wunused-variable]
         int u = 0;
             ^

Code

#include <iostream>
#include <algorithm>
#include <string>
#include <bits/stdc++.h>
#define N 1000000
using namespace std;
using llu = long long signed;
map<pair<llu, llu>, llu> traps;

llu m1[10];
llu m2[10];

llu* a = m1;
llu* b = m2;

inline bool is_trap_fi(llu up, llu d) {
    llu y = d + 1;
    llu x = up - y + 1;
    bool b = traps.find(make_pair(x, y)) != traps.end();
    if (b) {
        int u = 0;
    }
    return b;
}

inline bool is_trap_se(llu up, llu d, llu n) {
    llu y = n - up + d + 1;
    llu x = n - d;
    bool b = traps.find(make_pair(x, y)) != traps.end();
    if (b) {
        int u = 0;
    }
    return b;
}


llu g(llu n) {
    a[0] = 1;
    for (llu up = 1; up <= n ; ++up) {
        for (llu d = 0; d < up; ++d) {
            if (is_trap_se(up, d, n)) {
                b[d] = 0;
                continue;
            }

            if (d==0) {
                b[d] = a[d];
            } else if (d==up) {
                b[d] = a[d-1];
            }
            else {
                b[d] = a[d]+a[d-1];
            }
        }
        swap(a, b);
    }
    for (llu up = n - 1; up >= 1 ; --up) {
        for (llu d = 0; d < up; ++d) {
            if (is_trap_fi(up, d)) {
                b[d] = 0;
                continue;
            }
            b[d] = a[d]+a[d+1];
        }
        swap(a, b);
    }
    return a[0];
}


int main()
{
    llu n, traplen;

    cin >> n >> traplen;

    for (llu i = 0; i < traplen; i++ ) {
        llu a, b;
        cin >> a >> b;
        traps[make_pair(a,b)] = 1;
    }
    llu result = g(n);
    cout << result << endl;
    return 0;
}

Test details

Test 1

Verdict:

input
100 1000
41 11
11 24
51 72
47 31
...

correct output
342758070

user output
(empty)

Test 2

Verdict:

input
100 1000
83 37
24 1
52 42
86 36
...

correct output
919249325

user output
(empty)

Test 3

Verdict:

input
100 1000
99 28
16 31
92 41
39 65
...

correct output
12649242

user output
(empty)

Test 4

Verdict:

input
100 1000
5 47
32 1
27 70
86 39
...

correct output
466313473

user output
(empty)

Test 5

Verdict:

input
100 1000
14 28
63 16
15 54
68 18
...

correct output
525088588

user output
(empty)

Test 6

Verdict:

input
1000000 1000
332974 646000
669874 23872
662362 92533
670177 367382
...

correct output
476425733

user output
(empty)

Test 7

Verdict:

input
1000000 1000
474616 793877
452016 207512
940198 719201
162471 997296
...

correct output
757933231

user output
(empty)

Test 8

Verdict:

input
1000000 1000
125814 37785
523915 416397
246681 345297
635386 245404
...

correct output
672607703

user output
(empty)

Test 9

Verdict:

input
1000000 1000
468197 471455
970002 408761
420246 765021
8126 930827
...

correct output
138494458

user output
(empty)

Test 10

Verdict:

input
1000000 1000
837278 905086
893778 245584
867013 721507
404988 868333
...

correct output
796948966

user output
(empty)