oj.uz

Submission #722016

# Submission time Handle Problem Language Result Execution time Memory
722016 2023-04-11T10:30:13 Z n0sk1ll Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 331 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=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*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 52 ms 94932 KB Output is correct
2 Correct 51 ms 94884 KB Output is correct
3 Correct 57 ms 94860 KB Output is correct
4 Correct 50 ms 94936 KB Output is correct
5 Correct 46 ms 94872 KB Output is correct
6 Correct 46 ms 94916 KB Output is correct
7 Correct 46 ms 94900 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 94868 KB Output is correct
2 Correct 58 ms 94924 KB Output is correct
3 Correct 55 ms 94932 KB Output is correct
4 Correct 47 ms 94928 KB Output is correct
5 Correct 48 ms 94864 KB Output is correct
6 Correct 49 ms 94936 KB Output is correct
7 Correct 48 ms 95044 KB Output is correct
8 Correct 48 ms 94952 KB Output is correct
9 Correct 47 ms 94840 KB Output is correct
10 Correct 51 ms 94984 KB Output is correct
11 Correct 62 ms 95048 KB Output is correct
12 Correct 50 ms 94924 KB Output is correct
13 Correct 49 ms 95040 KB Output is correct
14 Correct 48 ms 95120 KB Output is correct
15 Correct 49 ms 95068 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 94844 KB Output is correct
2 Correct 55 ms 94852 KB Output is correct
3 Correct 54 ms 94852 KB Output is correct
4 Correct 53 ms 94924 KB Output is correct
5 Correct 46 ms 94824 KB Output is correct
6 Correct 50 ms 94820 KB Output is correct
7 Correct 50 ms 94852 KB Output is correct
8 Correct 47 ms 94888 KB Output is correct
9 Correct 49 ms 94948 KB Output is correct
10 Correct 56 ms 94888 KB Output is correct
11 Correct 55 ms 95084 KB Output is correct
12 Correct 47 ms 94924 KB Output is correct
13 Correct 48 ms 95180 KB Output is correct
14 Correct 48 ms 95052 KB Output is correct
15 Correct 48 ms 95052 KB Output is correct
16 Correct 47 ms 94984 KB Output is correct
17 Correct 48 ms 95308 KB Output is correct
18 Correct 63 ms 95076 KB Output is correct
19 Correct 69 ms 94920 KB Output is correct
20 Correct 144 ms 149196 KB Output is correct
21 Correct 47 ms 94936 KB Output is correct
22 Correct 53 ms 94980 KB Output is correct
23 Correct 51 ms 95052 KB Output is correct
24 Correct 52 ms 95136 KB Output is correct
25 Correct 51 ms 95068 KB Output is correct
26 Correct 48 ms 95168 KB Output is correct
27 Correct 52 ms 95068 KB Output is correct
28 Correct 50 ms 95868 KB Output is correct
29 Correct 49 ms 95908 KB Output is correct
30 Correct 47 ms 95308 KB Output is correct
31 Correct 56 ms 95520 KB Output is correct
32 Correct 55 ms 95388 KB Output is correct
33 Correct 54 ms 96716 KB Output is correct
34 Correct 51 ms 96724 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 94924 KB Output is correct
2 Correct 47 ms 94944 KB Output is correct
3 Correct 50 ms 94868 KB Output is correct
4 Correct 51 ms 94860 KB Output is correct
5 Correct 60 ms 94924 KB Output is correct
6 Correct 49 ms 94944 KB Output is correct
7 Correct 47 ms 94932 KB Output is correct
8 Correct 53 ms 94916 KB Output is correct
9 Correct 48 ms 94916 KB Output is correct
10 Correct 48 ms 94976 KB Output is correct
11 Correct 48 ms 95012 KB Output is correct
12 Correct 51 ms 94980 KB Output is correct
13 Correct 48 ms 95152 KB Output is correct
14 Correct 52 ms 95064 KB Output is correct
15 Correct 51 ms 95052 KB Output is correct
16 Correct 50 ms 94936 KB Output is correct
17 Correct 57 ms 95316 KB Output is correct
18 Correct 57 ms 95060 KB Output is correct
19 Correct 66 ms 95032 KB Output is correct
20 Correct 151 ms 149048 KB Output is correct
21 Correct 52 ms 94980 KB Output is correct
22 Correct 63 ms 94924 KB Output is correct
23 Correct 47 ms 95032 KB Output is correct
24 Correct 47 ms 95164 KB Output is correct
25 Correct 50 ms 95128 KB Output is correct
26 Correct 51 ms 95148 KB Output is correct
27 Correct 54 ms 95080 KB Output is correct
28 Correct 61 ms 95780 KB Output is correct
29 Correct 51 ms 95892 KB Output is correct
30 Correct 47 ms 95316 KB Output is correct
31 Correct 48 ms 95564 KB Output is correct
32 Correct 49 ms 95324 KB Output is correct
33 Correct 55 ms 96724 KB Output is correct
34 Correct 51 ms 96676 KB Output is correct
35 Correct 63 ms 98288 KB Output is correct
36 Correct 60 ms 95388 KB Output is correct
37 Correct 65 ms 99808 KB Output is correct
38 Correct 65 ms 99360 KB Output is correct
39 Correct 65 ms 98888 KB Output is correct
40 Correct 65 ms 98860 KB Output is correct
41 Correct 69 ms 98944 KB Output is correct
42 Correct 49 ms 95068 KB Output is correct
43 Correct 59 ms 95104 KB Output is correct
44 Correct 154 ms 149064 KB Output is correct
45 Correct 78 ms 102860 KB Output is correct
46 Correct 71 ms 102952 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 94836 KB Output is correct
2 Correct 47 ms 94924 KB Output is correct
3 Correct 49 ms 94816 KB Output is correct
4 Correct 49 ms 94840 KB Output is correct
5 Correct 52 ms 94924 KB Output is correct
6 Correct 51 ms 94920 KB Output is correct
7 Correct 47 ms 94852 KB Output is correct
8 Correct 48 ms 94944 KB Output is correct
9 Correct 47 ms 94860 KB Output is correct
10 Correct 70 ms 94924 KB Output is correct
11 Correct 52 ms 95080 KB Output is correct
12 Correct 60 ms 94908 KB Output is correct
13 Correct 49 ms 95100 KB Output is correct
14 Correct 48 ms 95128 KB Output is correct
15 Correct 58 ms 95056 KB Output is correct
16 Correct 50 ms 95008 KB Output is correct
17 Correct 56 ms 95368 KB Output is correct
18 Correct 67 ms 94996 KB Output is correct
19 Correct 64 ms 94984 KB Output is correct
20 Correct 143 ms 149108 KB Output is correct
21 Correct 49 ms 94900 KB Output is correct
22 Correct 52 ms 94924 KB Output is correct
23 Correct 49 ms 95068 KB Output is correct
24 Correct 52 ms 95248 KB Output is correct
25 Correct 51 ms 95088 KB Output is correct
26 Correct 51 ms 95052 KB Output is correct
27 Correct 47 ms 95100 KB Output is correct
28 Correct 62 ms 95820 KB Output is correct
29 Correct 54 ms 95872 KB Output is correct
30 Correct 51 ms 95304 KB Output is correct
31 Correct 48 ms 95592 KB Output is correct
32 Correct 47 ms 95412 KB Output is correct
33 Correct 52 ms 96736 KB Output is correct
34 Correct 55 ms 96792 KB Output is correct
35 Correct 66 ms 98284 KB Output is correct
36 Correct 49 ms 95344 KB Output is correct
37 Correct 61 ms 99824 KB Output is correct
38 Correct 67 ms 99252 KB Output is correct
39 Correct 68 ms 98872 KB Output is correct
40 Correct 67 ms 98948 KB Output is correct
41 Correct 82 ms 98944 KB Output is correct
42 Correct 53 ms 95132 KB Output is correct
43 Correct 52 ms 95056 KB Output is correct
44 Correct 156 ms 149140 KB Output is correct
45 Correct 83 ms 102952 KB Output is correct
46 Correct 86 ms 102900 KB Output is correct
47 Correct 86 ms 108980 KB Output is correct
48 Correct 243 ms 98360 KB Output is correct
49 Correct 293 ms 97676 KB Output is correct
50 Correct 271 ms 97316 KB Output is correct
51 Correct 99 ms 101852 KB Output is correct
52 Correct 77 ms 102872 KB Output is correct
53 Correct 64 ms 97884 KB Output is correct
54 Correct 272 ms 95592 KB Output is correct
55 Correct 310 ms 96568 KB Output is correct
56 Runtime error 331 ms 262144 KB Execution killed with signal 9
57 Halted 0 ms 0 KB -