oj.uz

Submission #721619

# Submission time Handle Problem Language Result Execution time Memory
721619 2023-04-11T05:38:53 Z n0sk1ll Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 376 ms 262144 KB 
#include <bits/stdc++.h>

#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)

using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
//const int mod = 1000000007;







//Note to self: Check for overflow

vector<pii> g[30003];
bool vis[30003];

vector<int> dat[2200006];

int main()
{
    FAST;

    int n,m; cin>>n>>m;
    set<pii> doges;

    int s,t;
    ff(i,0,m)
    {
        int b,p; cin>>b>>p;
        doges.insert({b,p});
        if (i==0) s=b;
        if (i==1) t=b;
    }

    for (auto [b,p] : doges)
    {
        for (int i=1;;i++)
        {
            if (b+i*p>=n) break;
            g[b].pb({b+i*p,i});
        }
        for (int i=1;;i++)
        {
            if (b-i*p<0) break;
            g[b].pb({b-i*p,i});
        }
    }

    dat[0].pb(s);
    fff(d,0,2'000'000)
    {
        for (auto p : dat[d])
        {
            if (vis[p]) continue; vis[p]=1;
            if (p==t) return cout<<d,0;
            for (auto it : g[p]) dat[d+it.yy].pb(it.xx);
        }
        dat[d].clear();
    }

    cout<<-1;
}

//Note to self: Check for overflow

/*

5 3
0 2
1 1
4 1

*/

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:58:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   58 |     for (auto [b,p] : doges)
      |               ^
skyscraper.cpp:77:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   77 |             if (vis[p]) continue; vis[p]=1;
      |             ^~
skyscraper.cpp:77:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   77 |             if (vis[p]) continue; vis[p]=1;
      |                                   ^~~
skyscraper.cpp:78:13: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
   78 |             if (p==t) return cout<<d,0;
      |             ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 52640 KB Output is correct
2 Correct 25 ms 52692 KB Output is correct
3 Correct 25 ms 52796 KB Output is correct
4 Correct 32 ms 52564 KB Output is correct
5 Correct 26 ms 52696 KB Output is correct
6 Correct 25 ms 52652 KB Output is correct
7 Correct 26 ms 52684 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 52636 KB Output is correct
2 Correct 25 ms 52660 KB Output is correct
3 Correct 25 ms 52684 KB Output is correct
4 Correct 31 ms 52692 KB Output is correct
5 Correct 28 ms 52624 KB Output is correct
6 Correct 27 ms 52680 KB Output is correct
7 Correct 29 ms 52608 KB Output is correct
8 Correct 27 ms 52692 KB Output is correct
9 Correct 25 ms 52692 KB Output is correct
10 Correct 25 ms 52692 KB Output is correct
11 Correct 26 ms 52808 KB Output is correct
12 Correct 25 ms 52692 KB Output is correct
13 Correct 26 ms 52800 KB Output is correct
14 Correct 26 ms 52820 KB Output is correct
15 Correct 27 ms 52820 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 52604 KB Output is correct
2 Correct 26 ms 52624 KB Output is correct
3 Correct 26 ms 52676 KB Output is correct
4 Correct 31 ms 52692 KB Output is correct
5 Correct 35 ms 52620 KB Output is correct
6 Correct 25 ms 52692 KB Output is correct
7 Correct 27 ms 52556 KB Output is correct
8 Correct 27 ms 52692 KB Output is correct
9 Correct 27 ms 52596 KB Output is correct
10 Correct 26 ms 52692 KB Output is correct
11 Correct 26 ms 52948 KB Output is correct
12 Correct 28 ms 52608 KB Output is correct
13 Correct 28 ms 52848 KB Output is correct
14 Correct 27 ms 52872 KB Output is correct
15 Correct 27 ms 52768 KB Output is correct
16 Correct 31 ms 52692 KB Output is correct
17 Correct 26 ms 53076 KB Output is correct
18 Correct 32 ms 52732 KB Output is correct
19 Correct 31 ms 52692 KB Output is correct
20 Correct 118 ms 106828 KB Output is correct
21 Correct 32 ms 52768 KB Output is correct
22 Correct 32 ms 52784 KB Output is correct
23 Correct 27 ms 52836 KB Output is correct
24 Correct 27 ms 52932 KB Output is correct
25 Correct 27 ms 52884 KB Output is correct
26 Correct 26 ms 52896 KB Output is correct
27 Correct 26 ms 52884 KB Output is correct
28 Correct 28 ms 53580 KB Output is correct
29 Correct 27 ms 53636 KB Output is correct
30 Correct 27 ms 53080 KB Output is correct
31 Correct 27 ms 53292 KB Output is correct
32 Correct 27 ms 53076 KB Output is correct
33 Correct 30 ms 54488 KB Output is correct
34 Correct 29 ms 54480 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 52692 KB Output is correct
2 Correct 26 ms 52556 KB Output is correct
3 Correct 26 ms 52692 KB Output is correct
4 Correct 31 ms 52696 KB Output is correct
5 Correct 26 ms 52672 KB Output is correct
6 Correct 26 ms 52692 KB Output is correct
7 Correct 26 ms 52596 KB Output is correct
8 Correct 26 ms 52608 KB Output is correct
9 Correct 27 ms 52692 KB Output is correct
10 Correct 27 ms 52724 KB Output is correct
11 Correct 26 ms 52864 KB Output is correct
12 Correct 26 ms 52692 KB Output is correct
13 Correct 26 ms 52780 KB Output is correct
14 Correct 26 ms 52820 KB Output is correct
15 Correct 27 ms 52820 KB Output is correct
16 Correct 32 ms 52668 KB Output is correct
17 Correct 28 ms 53116 KB Output is correct
18 Correct 32 ms 52820 KB Output is correct
19 Correct 32 ms 52688 KB Output is correct
20 Correct 121 ms 106840 KB Output is correct
21 Correct 32 ms 52768 KB Output is correct
22 Correct 32 ms 52756 KB Output is correct
23 Correct 26 ms 52768 KB Output is correct
24 Correct 28 ms 53008 KB Output is correct
25 Correct 27 ms 52836 KB Output is correct
26 Correct 26 ms 52796 KB Output is correct
27 Correct 29 ms 52792 KB Output is correct
28 Correct 28 ms 53588 KB Output is correct
29 Correct 27 ms 53636 KB Output is correct
30 Correct 26 ms 53032 KB Output is correct
31 Correct 27 ms 53328 KB Output is correct
32 Correct 31 ms 53116 KB Output is correct
33 Correct 31 ms 54484 KB Output is correct
34 Correct 29 ms 54488 KB Output is correct
35 Correct 43 ms 55992 KB Output is correct
36 Correct 29 ms 53076 KB Output is correct
37 Correct 41 ms 57508 KB Output is correct
38 Correct 44 ms 57064 KB Output is correct
39 Correct 42 ms 56640 KB Output is correct
40 Correct 44 ms 56664 KB Output is correct
41 Correct 46 ms 56712 KB Output is correct
42 Correct 31 ms 52876 KB Output is correct
43 Correct 29 ms 52852 KB Output is correct
44 Correct 125 ms 106856 KB Output is correct
45 Correct 49 ms 60620 KB Output is correct
46 Correct 47 ms 60672 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 52648 KB Output is correct
2 Correct 27 ms 52604 KB Output is correct
3 Correct 26 ms 52640 KB Output is correct
4 Correct 32 ms 52676 KB Output is correct
5 Correct 26 ms 52624 KB Output is correct
6 Correct 29 ms 52560 KB Output is correct
7 Correct 26 ms 52572 KB Output is correct
8 Correct 28 ms 52612 KB Output is correct
9 Correct 26 ms 52636 KB Output is correct
10 Correct 26 ms 52656 KB Output is correct
11 Correct 26 ms 52820 KB Output is correct
12 Correct 26 ms 52584 KB Output is correct
13 Correct 26 ms 52872 KB Output is correct
14 Correct 27 ms 52820 KB Output is correct
15 Correct 28 ms 52816 KB Output is correct
16 Correct 33 ms 52748 KB Output is correct
17 Correct 27 ms 53068 KB Output is correct
18 Correct 34 ms 52740 KB Output is correct
19 Correct 32 ms 52760 KB Output is correct
20 Correct 118 ms 106828 KB Output is correct
21 Correct 32 ms 52668 KB Output is correct
22 Correct 32 ms 52684 KB Output is correct
23 Correct 26 ms 52820 KB Output is correct
24 Correct 27 ms 52936 KB Output is correct
25 Correct 28 ms 52820 KB Output is correct
26 Correct 28 ms 52808 KB Output is correct
27 Correct 26 ms 52820 KB Output is correct
28 Correct 31 ms 53588 KB Output is correct
29 Correct 27 ms 53624 KB Output is correct
30 Correct 26 ms 52944 KB Output is correct
31 Correct 30 ms 53244 KB Output is correct
32 Correct 26 ms 53072 KB Output is correct
33 Correct 29 ms 54420 KB Output is correct
34 Correct 29 ms 54420 KB Output is correct
35 Correct 39 ms 56008 KB Output is correct
36 Correct 27 ms 53020 KB Output is correct
37 Correct 40 ms 57476 KB Output is correct
38 Correct 46 ms 56964 KB Output is correct
39 Correct 42 ms 56528 KB Output is correct
40 Correct 43 ms 56652 KB Output is correct
41 Correct 44 ms 56652 KB Output is correct
42 Correct 33 ms 52836 KB Output is correct
43 Correct 30 ms 52852 KB Output is correct
44 Correct 122 ms 106788 KB Output is correct
45 Correct 50 ms 60584 KB Output is correct
46 Correct 49 ms 60612 KB Output is correct
47 Correct 59 ms 66660 KB Output is correct
48 Correct 48 ms 56036 KB Output is correct
49 Correct 44 ms 55124 KB Output is correct
50 Correct 43 ms 54840 KB Output is correct
51 Correct 53 ms 59244 KB Output is correct
52 Correct 55 ms 60236 KB Output is correct
53 Correct 41 ms 55340 KB Output is correct
54 Correct 32 ms 53412 KB Output is correct
55 Correct 34 ms 54096 KB Output is correct
56 Runtime error 376 ms 262144 KB Execution killed with signal 9
57 Halted 0 ms 0 KB -