oj.uz

Submission #722014

# Submission time Handle Problem Language Result Execution time Memory
722014 2023-04-11T10:28:58 Z n0sk1ll Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 1000 ms 149368 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=2'000'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*m)
    {
        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 47 ms 94996 KB Output is correct
2 Correct 48 ms 94876 KB Output is correct
3 Correct 48 ms 94936 KB Output is correct
4 Correct 48 ms 94932 KB Output is correct
5 Correct 56 ms 94824 KB Output is correct
6 Correct 47 ms 94932 KB Output is correct
7 Correct 46 ms 94856 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 94824 KB Output is correct
2 Correct 48 ms 94848 KB Output is correct
3 Correct 52 ms 94896 KB Output is correct
4 Correct 54 ms 94928 KB Output is correct
5 Correct 46 ms 94924 KB Output is correct
6 Correct 47 ms 94868 KB Output is correct
7 Correct 47 ms 94860 KB Output is correct
8 Correct 45 ms 94988 KB Output is correct
9 Correct 48 ms 94876 KB Output is correct
10 Correct 51 ms 94880 KB Output is correct
11 Correct 49 ms 94988 KB Output is correct
12 Correct 46 ms 94912 KB Output is correct
13 Correct 48 ms 95088 KB Output is correct
14 Correct 47 ms 95080 KB Output is correct
15 Correct 52 ms 95028 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 95052 KB Output is correct
2 Correct 50 ms 94860 KB Output is correct
3 Correct 46 ms 94920 KB Output is correct
4 Correct 47 ms 94940 KB Output is correct
5 Correct 46 ms 94920 KB Output is correct
6 Correct 45 ms 94936 KB Output is correct
7 Correct 52 ms 94828 KB Output is correct
8 Correct 48 ms 94940 KB Output is correct
9 Correct 52 ms 94904 KB Output is correct
10 Correct 46 ms 94924 KB Output is correct
11 Correct 46 ms 95032 KB Output is correct
12 Correct 48 ms 94836 KB Output is correct
13 Correct 48 ms 95076 KB Output is correct
14 Correct 46 ms 95208 KB Output is correct
15 Correct 49 ms 95008 KB Output is correct
16 Correct 52 ms 95052 KB Output is correct
17 Correct 47 ms 95304 KB Output is correct
18 Correct 59 ms 95084 KB Output is correct
19 Correct 47 ms 94972 KB Output is correct
20 Correct 143 ms 149068 KB Output is correct
21 Correct 48 ms 95036 KB Output is correct
22 Correct 59 ms 94992 KB Output is correct
23 Correct 57 ms 95100 KB Output is correct
24 Correct 50 ms 95236 KB Output is correct
25 Correct 46 ms 95180 KB Output is correct
26 Correct 49 ms 95176 KB Output is correct
27 Correct 47 ms 95112 KB Output is correct
28 Correct 48 ms 95768 KB Output is correct
29 Correct 50 ms 95968 KB Output is correct
30 Correct 46 ms 95224 KB Output is correct
31 Correct 60 ms 95572 KB Output is correct
32 Correct 55 ms 95356 KB Output is correct
33 Correct 52 ms 96780 KB Output is correct
34 Correct 52 ms 96744 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 94856 KB Output is correct
2 Correct 49 ms 94932 KB Output is correct
3 Correct 51 ms 94872 KB Output is correct
4 Correct 62 ms 94844 KB Output is correct
5 Correct 53 ms 94912 KB Output is correct
6 Correct 55 ms 94936 KB Output is correct
7 Correct 51 ms 94924 KB Output is correct
8 Correct 48 ms 94940 KB Output is correct
9 Correct 51 ms 94948 KB Output is correct
10 Correct 49 ms 94924 KB Output is correct
11 Correct 56 ms 95076 KB Output is correct
12 Correct 47 ms 94860 KB Output is correct
13 Correct 48 ms 95104 KB Output is correct
14 Correct 49 ms 95052 KB Output is correct
15 Correct 51 ms 95104 KB Output is correct
16 Correct 48 ms 94988 KB Output is correct
17 Correct 52 ms 95280 KB Output is correct
18 Correct 56 ms 95068 KB Output is correct
19 Correct 52 ms 95028 KB Output is correct
20 Correct 147 ms 149180 KB Output is correct
21 Correct 47 ms 94924 KB Output is correct
22 Correct 51 ms 95060 KB Output is correct
23 Correct 49 ms 95080 KB Output is correct
24 Correct 49 ms 95272 KB Output is correct
25 Correct 54 ms 95180 KB Output is correct
26 Correct 50 ms 95200 KB Output is correct
27 Correct 49 ms 95052 KB Output is correct
28 Correct 57 ms 95832 KB Output is correct
29 Correct 54 ms 95988 KB Output is correct
30 Correct 50 ms 95456 KB Output is correct
31 Correct 55 ms 95476 KB Output is correct
32 Correct 50 ms 95392 KB Output is correct
33 Correct 53 ms 96780 KB Output is correct
34 Correct 53 ms 96776 KB Output is correct
35 Correct 71 ms 98412 KB Output is correct
36 Correct 50 ms 95360 KB Output is correct
37 Correct 65 ms 99916 KB Output is correct
38 Correct 68 ms 99524 KB Output is correct
39 Correct 68 ms 99172 KB Output is correct
40 Correct 74 ms 99080 KB Output is correct
41 Correct 70 ms 99276 KB Output is correct
42 Correct 57 ms 95284 KB Output is correct
43 Correct 52 ms 95260 KB Output is correct
44 Correct 156 ms 149296 KB Output is correct
45 Correct 75 ms 103080 KB Output is correct
46 Correct 76 ms 103048 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 94920 KB Output is correct
2 Correct 50 ms 94920 KB Output is correct
3 Correct 53 ms 94888 KB Output is correct
4 Correct 54 ms 94844 KB Output is correct
5 Correct 47 ms 94836 KB Output is correct
6 Correct 50 ms 94940 KB Output is correct
7 Correct 50 ms 94920 KB Output is correct
8 Correct 48 ms 94944 KB Output is correct
9 Correct 51 ms 94968 KB Output is correct
10 Correct 51 ms 94932 KB Output is correct
11 Correct 49 ms 95092 KB Output is correct
12 Correct 48 ms 94952 KB Output is correct
13 Correct 50 ms 95088 KB Output is correct
14 Correct 50 ms 95052 KB Output is correct
15 Correct 50 ms 95108 KB Output is correct
16 Correct 48 ms 95044 KB Output is correct
17 Correct 49 ms 95404 KB Output is correct
18 Correct 56 ms 95084 KB Output is correct
19 Correct 57 ms 94952 KB Output is correct
20 Correct 148 ms 149240 KB Output is correct
21 Correct 48 ms 94996 KB Output is correct
22 Correct 54 ms 95028 KB Output is correct
23 Correct 50 ms 95208 KB Output is correct
24 Correct 53 ms 95236 KB Output is correct
25 Correct 52 ms 95180 KB Output is correct
26 Correct 47 ms 95180 KB Output is correct
27 Correct 48 ms 95088 KB Output is correct
28 Correct 50 ms 95792 KB Output is correct
29 Correct 49 ms 95920 KB Output is correct
30 Correct 55 ms 95328 KB Output is correct
31 Correct 54 ms 95712 KB Output is correct
32 Correct 48 ms 95320 KB Output is correct
33 Correct 52 ms 96804 KB Output is correct
34 Correct 53 ms 96712 KB Output is correct
35 Correct 63 ms 98472 KB Output is correct
36 Correct 50 ms 95432 KB Output is correct
37 Correct 64 ms 99964 KB Output is correct
38 Correct 69 ms 99628 KB Output is correct
39 Correct 65 ms 99148 KB Output is correct
40 Correct 70 ms 99104 KB Output is correct
41 Correct 69 ms 99168 KB Output is correct
42 Correct 52 ms 95412 KB Output is correct
43 Correct 57 ms 95328 KB Output is correct
44 Correct 157 ms 149368 KB Output is correct
45 Correct 82 ms 103084 KB Output is correct
46 Correct 90 ms 103176 KB Output is correct
47 Correct 100 ms 109180 KB Output is correct
48 Execution timed out 1072 ms 98632 KB Time limit exceeded
49 Halted 0 ms 0 KB -