Submission #166851

# Submission time Handle Problem Language Result Execution time Memory
166851 2019-12-04T10:48:47 Z Hideo Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
455 ms 262144 KB
// Need to git gud and reach 1900+
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
using namespace std;

#define all(s) s.begin(), s.end()
#define ok puts("ok")
#define ll long long
#define pb push_back
#define mk make_pair
#define fr first
#define sc second
#define vi vector < int >
#define pi pair < int, int >
#define prev prev123
#define next next123
#define pow pow123
#define left left123
#define right right123

const int N = 30007;
const int M = 8e6 + 7;
const int INF = 1e9 + 7;

pi a[N];
int d[M];
int m, n, s, f;

vector < pi > g[M];

main(){ // If you don't know what to do, check the text box at the bottom
    cin >> m >> n;
    for (int i = 1; i <= n; i++){
        scanf("%d%d", &a[i].fr, &a[i].sc);
        a[i].fr++;
    }
    s = a[1].fr, f = a[2].fr;
    sort(a + 1, a + n + 1);
    int k = unique(a + 1, a + n + 1) - a;
    for (int i = 1; i < k; i++){
        if (a[i].sc <= 250)
            g[a[i].fr].pb(mk(m + (a[i].fr - 1) * 250 + a[i].sc, 0));
        else {
            int pos = a[i].fr, pw = a[i].sc, c = 0;
            while (pos + pw <= m){
                pos += pw; c++;
                g[a[i].fr].pb(mk(pos, c));
            }
            pos = a[i].fr, c = 0;
            while (pos - pw > 0){
                pos -= pw; c++;
                g[a[i].fr].pb(mk(pos, c));
            }
        }
    }
    for (int i = 1; i <= m; i++){
        for (int j = 1; j <= 250; j++){
            if (i + j <= m){
                g[m + (i - 1) * 250 + j].pb(mk(m + (i + j - 1) * 250 + j, 1));
                g[m + (i - 1) * 250 + j].pb(mk(i + j, 1));
            }
            if (i - j > 0){
                g[m + (i - 1) * 250 + j].pb(mk(m + (i - j - 1) * 250 + j, 1));
                g[m + (i - 1) * 250 + j].pb(mk(i - j, 1));
            }
        }
    }
    priority_queue < pi > pq;
    pq.push(mk(0, s));
    memset(d, 0x3f3f3f3f, sizeof(d));
    d[s] = 0;
    while (!pq.empty()){
        int w = -pq.top().fr, v = pq.top().sc;
        pq.pop();
        if (d[v] < w)
            continue;
        for (pi to : g[v]){
            if (d[to.fr] > d[v] + to.sc){
                d[to.fr] = d[v] + to.sc;
                pq.push(mk(-d[to.fr], to.fr));
            }
        }
    }
    if (d[f] != d[0])
        printf("%d", d[f]);
    else
        puts("-1");
}

/*
    Totally not inspired by BenQ's template
    Things you should do:
    1. Look for stupid typos in code e.g 1 instead of -1 etc
    2. Check if there is no infinite loops
    3. "Measure twice, cut once"
    4. Stay focused
*/

Compilation message

skyscraper.cpp:33:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){ // If you don't know what to do, check the text box at the bottom
      ^
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:36:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &a[i].fr, &a[i].sc);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 228 ms 219640 KB Output is correct
2 Correct 229 ms 219516 KB Output is correct
3 Correct 226 ms 219596 KB Output is correct
4 Correct 228 ms 219512 KB Output is correct
5 Correct 251 ms 219512 KB Output is correct
6 Correct 224 ms 219444 KB Output is correct
7 Correct 230 ms 219432 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 245 ms 219480 KB Output is correct
2 Correct 229 ms 219724 KB Output is correct
3 Correct 231 ms 219816 KB Output is correct
4 Correct 227 ms 219584 KB Output is correct
5 Correct 228 ms 219532 KB Output is correct
6 Correct 231 ms 219596 KB Output is correct
7 Correct 224 ms 219524 KB Output is correct
8 Correct 233 ms 219704 KB Output is correct
9 Correct 235 ms 219640 KB Output is correct
10 Correct 235 ms 219824 KB Output is correct
11 Correct 239 ms 219916 KB Output is correct
12 Correct 236 ms 219908 KB Output is correct
13 Correct 238 ms 219768 KB Output is correct
14 Correct 234 ms 219764 KB Output is correct
15 Correct 247 ms 219896 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 225 ms 219512 KB Output is correct
2 Correct 241 ms 219512 KB Output is correct
3 Correct 230 ms 219512 KB Output is correct
4 Correct 235 ms 219512 KB Output is correct
5 Correct 233 ms 219512 KB Output is correct
6 Correct 236 ms 219600 KB Output is correct
7 Correct 233 ms 219636 KB Output is correct
8 Correct 234 ms 219512 KB Output is correct
9 Correct 235 ms 219512 KB Output is correct
10 Correct 231 ms 219896 KB Output is correct
11 Correct 235 ms 219768 KB Output is correct
12 Correct 238 ms 219868 KB Output is correct
13 Correct 237 ms 220008 KB Output is correct
14 Correct 235 ms 219912 KB Output is correct
15 Correct 234 ms 219904 KB Output is correct
16 Correct 235 ms 220672 KB Output is correct
17 Correct 267 ms 227408 KB Output is correct
18 Correct 306 ms 239096 KB Output is correct
19 Correct 319 ms 242092 KB Output is correct
20 Correct 334 ms 242164 KB Output is correct
21 Correct 261 ms 223196 KB Output is correct
22 Correct 307 ms 239480 KB Output is correct
23 Correct 302 ms 237276 KB Output is correct
24 Correct 319 ms 240940 KB Output is correct
25 Correct 338 ms 242040 KB Output is correct
26 Correct 322 ms 242060 KB Output is correct
27 Correct 321 ms 242004 KB Output is correct
28 Correct 326 ms 242304 KB Output is correct
29 Correct 330 ms 242016 KB Output is correct
30 Correct 322 ms 242068 KB Output is correct
31 Correct 328 ms 242016 KB Output is correct
32 Correct 325 ms 242212 KB Output is correct
33 Correct 368 ms 242180 KB Output is correct
34 Correct 356 ms 242296 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 234 ms 219460 KB Output is correct
2 Correct 229 ms 219512 KB Output is correct
3 Correct 232 ms 219516 KB Output is correct
4 Correct 235 ms 219640 KB Output is correct
5 Correct 234 ms 219540 KB Output is correct
6 Correct 234 ms 219504 KB Output is correct
7 Correct 233 ms 219516 KB Output is correct
8 Correct 234 ms 219640 KB Output is correct
9 Correct 233 ms 219776 KB Output is correct
10 Correct 233 ms 219828 KB Output is correct
11 Correct 234 ms 219768 KB Output is correct
12 Correct 238 ms 219768 KB Output is correct
13 Correct 227 ms 219948 KB Output is correct
14 Correct 234 ms 219888 KB Output is correct
15 Correct 230 ms 219752 KB Output is correct
16 Correct 233 ms 220696 KB Output is correct
17 Correct 267 ms 227288 KB Output is correct
18 Correct 300 ms 239096 KB Output is correct
19 Correct 314 ms 242048 KB Output is correct
20 Correct 318 ms 242040 KB Output is correct
21 Correct 238 ms 223224 KB Output is correct
22 Correct 308 ms 239608 KB Output is correct
23 Correct 303 ms 237344 KB Output is correct
24 Correct 318 ms 241056 KB Output is correct
25 Correct 321 ms 242040 KB Output is correct
26 Correct 324 ms 242040 KB Output is correct
27 Correct 313 ms 242228 KB Output is correct
28 Correct 322 ms 242092 KB Output is correct
29 Correct 325 ms 242024 KB Output is correct
30 Correct 318 ms 242052 KB Output is correct
31 Correct 342 ms 242040 KB Output is correct
32 Correct 318 ms 242140 KB Output is correct
33 Correct 354 ms 242040 KB Output is correct
34 Correct 352 ms 242296 KB Output is correct
35 Correct 324 ms 235896 KB Output is correct
36 Correct 282 ms 231416 KB Output is correct
37 Correct 371 ms 242296 KB Output is correct
38 Correct 366 ms 242936 KB Output is correct
39 Correct 366 ms 242956 KB Output is correct
40 Correct 369 ms 242808 KB Output is correct
41 Correct 366 ms 242904 KB Output is correct
42 Correct 319 ms 242192 KB Output is correct
43 Correct 318 ms 242276 KB Output is correct
44 Correct 316 ms 242344 KB Output is correct
45 Correct 446 ms 242936 KB Output is correct
46 Correct 438 ms 243136 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 225 ms 219700 KB Output is correct
2 Correct 246 ms 219512 KB Output is correct
3 Correct 227 ms 219560 KB Output is correct
4 Correct 236 ms 219512 KB Output is correct
5 Correct 228 ms 219592 KB Output is correct
6 Correct 231 ms 219456 KB Output is correct
7 Correct 229 ms 219548 KB Output is correct
8 Correct 233 ms 219612 KB Output is correct
9 Correct 230 ms 219640 KB Output is correct
10 Correct 229 ms 219768 KB Output is correct
11 Correct 235 ms 219896 KB Output is correct
12 Correct 234 ms 219868 KB Output is correct
13 Correct 238 ms 219912 KB Output is correct
14 Correct 236 ms 219768 KB Output is correct
15 Correct 236 ms 219864 KB Output is correct
16 Correct 240 ms 220664 KB Output is correct
17 Correct 267 ms 227292 KB Output is correct
18 Correct 308 ms 239232 KB Output is correct
19 Correct 318 ms 242040 KB Output is correct
20 Correct 319 ms 242124 KB Output is correct
21 Correct 246 ms 223092 KB Output is correct
22 Correct 307 ms 239480 KB Output is correct
23 Correct 303 ms 237424 KB Output is correct
24 Correct 318 ms 240828 KB Output is correct
25 Correct 320 ms 242040 KB Output is correct
26 Correct 330 ms 242052 KB Output is correct
27 Correct 311 ms 242040 KB Output is correct
28 Correct 324 ms 242040 KB Output is correct
29 Correct 335 ms 242112 KB Output is correct
30 Correct 317 ms 242056 KB Output is correct
31 Correct 321 ms 242168 KB Output is correct
32 Correct 323 ms 242040 KB Output is correct
33 Correct 369 ms 242176 KB Output is correct
34 Correct 348 ms 242164 KB Output is correct
35 Correct 315 ms 235896 KB Output is correct
36 Correct 276 ms 231504 KB Output is correct
37 Correct 366 ms 242300 KB Output is correct
38 Correct 365 ms 242972 KB Output is correct
39 Correct 363 ms 242768 KB Output is correct
40 Correct 363 ms 242808 KB Output is correct
41 Correct 367 ms 242880 KB Output is correct
42 Correct 327 ms 242300 KB Output is correct
43 Correct 325 ms 242260 KB Output is correct
44 Correct 325 ms 242296 KB Output is correct
45 Correct 449 ms 243096 KB Output is correct
46 Correct 455 ms 242980 KB Output is correct
47 Runtime error 439 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
48 Halted 0 ms 0 KB -