oj.uz

Submission #722017

# Submission time Handle Problem Language Result Execution time Memory
722017 2023-04-11T10:31:01 Z n0sk1ll Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 420 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];

int km=0; const int sf=500'000;
vector<int> dat[2*sf+15];

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,n*1000)
    {
        if (d-km*sf>=sf)
        {
            ff(i,0,sf) dat[i]=dat[i+sf];
            ff(i,0,sf) dat[i+sf].clear();
            km++;
        }
        for (auto p : dat[d-km*sf])
        {
            if (vis[p]) continue; vis[p]=1;
            if (p==t) return cout<<d,0;
            for (auto it : g[p]) dat[d+it.yy-km*sf].pb(it.xx);
        }
        dat[d-km*sf].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:84:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   84 |             if (vis[p]) continue; vis[p]=1;
      |             ^~
skyscraper.cpp:84:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   84 |             if (vis[p]) continue; vis[p]=1;
      |                                   ^~~
skyscraper.cpp:85:13: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
   85 |             if (p==t) return cout<<d,0;
      |             ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 24404 KB Output is correct
2 Correct 14 ms 24496 KB Output is correct
3 Correct 14 ms 24404 KB Output is correct
4 Correct 13 ms 24472 KB Output is correct
5 Correct 13 ms 24404 KB Output is correct
6 Correct 13 ms 24496 KB Output is correct
7 Correct 13 ms 24524 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24404 KB Output is correct
2 Correct 14 ms 24512 KB Output is correct
3 Correct 16 ms 24488 KB Output is correct
4 Correct 14 ms 24508 KB Output is correct
5 Correct 13 ms 24404 KB Output is correct
6 Correct 13 ms 24448 KB Output is correct
7 Correct 13 ms 24404 KB Output is correct
8 Correct 13 ms 24404 KB Output is correct
9 Correct 12 ms 24404 KB Output is correct
10 Correct 12 ms 24532 KB Output is correct
11 Correct 13 ms 24628 KB Output is correct
12 Correct 13 ms 24520 KB Output is correct
13 Correct 14 ms 24660 KB Output is correct
14 Correct 14 ms 24660 KB Output is correct
15 Correct 17 ms 24660 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24404 KB Output is correct
2 Correct 16 ms 24388 KB Output is correct
3 Correct 13 ms 24404 KB Output is correct
4 Correct 13 ms 24464 KB Output is correct
5 Correct 17 ms 24452 KB Output is correct
6 Correct 13 ms 24404 KB Output is correct
7 Correct 16 ms 24476 KB Output is correct
8 Correct 14 ms 24404 KB Output is correct
9 Correct 14 ms 24516 KB Output is correct
10 Correct 15 ms 24532 KB Output is correct
11 Correct 16 ms 24576 KB Output is correct
12 Correct 14 ms 24520 KB Output is correct
13 Correct 14 ms 24624 KB Output is correct
14 Correct 14 ms 24684 KB Output is correct
15 Correct 14 ms 24624 KB Output is correct
16 Correct 14 ms 24660 KB Output is correct
17 Correct 20 ms 24936 KB Output is correct
18 Correct 27 ms 24584 KB Output is correct
19 Correct 30 ms 24488 KB Output is correct
20 Correct 117 ms 78608 KB Output is correct
21 Correct 16 ms 24580 KB Output is correct
22 Correct 29 ms 24516 KB Output is correct
23 Correct 13 ms 24596 KB Output is correct
24 Correct 14 ms 24816 KB Output is correct
25 Correct 14 ms 24728 KB Output is correct
26 Correct 14 ms 24732 KB Output is correct
27 Correct 15 ms 24612 KB Output is correct
28 Correct 16 ms 25304 KB Output is correct
29 Correct 15 ms 25544 KB Output is correct
30 Correct 13 ms 24788 KB Output is correct
31 Correct 16 ms 25048 KB Output is correct
32 Correct 15 ms 24920 KB Output is correct
33 Correct 23 ms 26300 KB Output is correct
34 Correct 19 ms 26324 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24404 KB Output is correct
2 Correct 13 ms 24512 KB Output is correct
3 Correct 12 ms 24504 KB Output is correct
4 Correct 12 ms 24504 KB Output is correct
5 Correct 13 ms 24404 KB Output is correct
6 Correct 15 ms 24468 KB Output is correct
7 Correct 13 ms 24404 KB Output is correct
8 Correct 13 ms 24404 KB Output is correct
9 Correct 15 ms 24404 KB Output is correct
10 Correct 12 ms 24532 KB Output is correct
11 Correct 13 ms 24660 KB Output is correct
12 Correct 12 ms 24404 KB Output is correct
13 Correct 14 ms 24660 KB Output is correct
14 Correct 13 ms 24684 KB Output is correct
15 Correct 14 ms 24660 KB Output is correct
16 Correct 15 ms 24588 KB Output is correct
17 Correct 15 ms 24916 KB Output is correct
18 Correct 31 ms 24532 KB Output is correct
19 Correct 31 ms 24552 KB Output is correct
20 Correct 115 ms 78676 KB Output is correct
21 Correct 18 ms 24584 KB Output is correct
22 Correct 26 ms 24520 KB Output is correct
23 Correct 13 ms 24660 KB Output is correct
24 Correct 15 ms 24812 KB Output is correct
25 Correct 19 ms 24660 KB Output is correct
26 Correct 15 ms 24612 KB Output is correct
27 Correct 13 ms 24660 KB Output is correct
28 Correct 16 ms 25428 KB Output is correct
29 Correct 14 ms 25428 KB Output is correct
30 Correct 14 ms 24836 KB Output is correct
31 Correct 14 ms 25044 KB Output is correct
32 Correct 16 ms 24836 KB Output is correct
33 Correct 17 ms 26352 KB Output is correct
34 Correct 17 ms 26272 KB Output is correct
35 Correct 29 ms 27732 KB Output is correct
36 Correct 21 ms 24940 KB Output is correct
37 Correct 34 ms 29276 KB Output is correct
38 Correct 32 ms 28884 KB Output is correct
39 Correct 33 ms 28456 KB Output is correct
40 Correct 31 ms 28396 KB Output is correct
41 Correct 30 ms 28576 KB Output is correct
42 Correct 17 ms 24740 KB Output is correct
43 Correct 21 ms 24700 KB Output is correct
44 Correct 131 ms 78700 KB Output is correct
45 Correct 38 ms 32504 KB Output is correct
46 Correct 35 ms 32512 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 24396 KB Output is correct
2 Correct 12 ms 24448 KB Output is correct
3 Correct 13 ms 24404 KB Output is correct
4 Correct 14 ms 24404 KB Output is correct
5 Correct 14 ms 24532 KB Output is correct
6 Correct 16 ms 24404 KB Output is correct
7 Correct 14 ms 24416 KB Output is correct
8 Correct 14 ms 24444 KB Output is correct
9 Correct 16 ms 24452 KB Output is correct
10 Correct 17 ms 24464 KB Output is correct
11 Correct 13 ms 24632 KB Output is correct
12 Correct 13 ms 24436 KB Output is correct
13 Correct 14 ms 24660 KB Output is correct
14 Correct 14 ms 24660 KB Output is correct
15 Correct 14 ms 24580 KB Output is correct
16 Correct 13 ms 24532 KB Output is correct
17 Correct 14 ms 24888 KB Output is correct
18 Correct 25 ms 24532 KB Output is correct
19 Correct 34 ms 24636 KB Output is correct
20 Correct 112 ms 78660 KB Output is correct
21 Correct 14 ms 24528 KB Output is correct
22 Correct 27 ms 24616 KB Output is correct
23 Correct 14 ms 24644 KB Output is correct
24 Correct 14 ms 24788 KB Output is correct
25 Correct 15 ms 24660 KB Output is correct
26 Correct 13 ms 24660 KB Output is correct
27 Correct 14 ms 24660 KB Output is correct
28 Correct 19 ms 25428 KB Output is correct
29 Correct 17 ms 25428 KB Output is correct
30 Correct 14 ms 24904 KB Output is correct
31 Correct 15 ms 25044 KB Output is correct
32 Correct 16 ms 24916 KB Output is correct
33 Correct 17 ms 26244 KB Output is correct
34 Correct 17 ms 26324 KB Output is correct
35 Correct 27 ms 27788 KB Output is correct
36 Correct 15 ms 24916 KB Output is correct
37 Correct 33 ms 29328 KB Output is correct
38 Correct 33 ms 28908 KB Output is correct
39 Correct 30 ms 28368 KB Output is correct
40 Correct 29 ms 28364 KB Output is correct
41 Correct 30 ms 28508 KB Output is correct
42 Correct 16 ms 24708 KB Output is correct
43 Correct 20 ms 24652 KB Output is correct
44 Correct 116 ms 78628 KB Output is correct
45 Correct 36 ms 32440 KB Output is correct
46 Correct 36 ms 32432 KB Output is correct
47 Correct 45 ms 38440 KB Output is correct
48 Correct 227 ms 27916 KB Output is correct
49 Correct 235 ms 26956 KB Output is correct
50 Correct 254 ms 26708 KB Output is correct
51 Correct 40 ms 31060 KB Output is correct
52 Correct 45 ms 32212 KB Output is correct
53 Correct 28 ms 27148 KB Output is correct
54 Correct 270 ms 25172 KB Output is correct
55 Correct 286 ms 25984 KB Output is correct
56 Runtime error 420 ms 262144 KB Execution killed with signal 9
57 Halted 0 ms 0 KB -