Submission #166855

#	Time	Username	Problem	Language	Result	Execution time	Memory
166855		Hideo	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1073 ms	27376 KiB

skyscraper

// 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 = 207;
const int INF = 1e9 + 7;

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

vector < int > lst[N];

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], &b[i]);
        lst[a[i] + 1].pb(b[i]);
    }
    s = a[1] + 1, f = a[2] + 1;
    priority_queue < pair < int, pi > > pq;
    pq.push(mk(0, mk(s, 0)));
    memset(d, 0x3f3f3f3f, sizeof(d));
    d[s][0] = 0;
    while (!pq.empty()){
        int w = -pq.top().fr, v = pq.top().sc.fr, pw = pq.top().sc.sc;
        pq.pop();
        if (d[v][pw] < w)
            continue;
        if (pw == 0){
            int pos = v, c = 0;
            for (int to : lst[v]){
                if (to > 200){
                    int pos = v, c = 0;
                    while (pos + to <= m){
                        pos += to; c++;
                        if (d[pos][0] > d[v][0] + c){
                            d[pos][0] = d[v][0] + c;
                            pq.push(mk(-d[pos][0], mk(pos, 0)));
                        }
                    }
                    pos = v, c = 0;
                    while (pos - to > 0){
                        pos -= to; c++;
                        if (d[pos][0] > d[v][0] + c){
                            d[pos][0] = d[v][0] + c;
                            pq.push(mk(-d[pos][0], mk(pos, 0)));
                        }
                    }
                }
                else {
                    if (d[v][to] > d[v][0]){
                        d[v][to] = d[v][0];
                        pq.push(mk(-d[v][to], mk(v, to)));
                    }
                }
            }
        }
        else {
            if (v + pw <= m && d[v + pw][pw] > d[v][pw] + 1){
                d[v + pw][pw] = d[v][pw] + 1;
                pq.push(mk(-d[v + pw][pw], mk(v + pw, pw)));
            }
            if (v + pw <= m && d[v + pw][0] > d[v][pw] + 1){
                d[v + pw][0] = d[v][pw] + 1;
                pq.push(mk(-d[v + pw][0], mk(v + pw, 0)));
            }
            if (v - pw > 0 && d[v - pw][pw] > d[v][pw] + 1){
                d[v - pw][pw] = d[v][pw] + 1;
                pq.push(mk(-d[v - pw][pw], mk(v - pw, pw)));
            }
            if (v - pw > 0 && d[v - pw][0] > d[v][pw] + 1){
                d[v - pw][0] = d[v][pw] + 1;
                pq.push(mk(-d[v - pw][0], mk(v - pw, 0)));
            }
        }
    }
    if (d[f][0] != d[0][0])
        printf("%d", d[f][0]);
    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 (stderr)

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:50:17: warning: unused variable 'pos' [-Wunused-variable]
             int pos = v, c = 0;
                 ^~~
skyscraper.cpp:50:26: warning: unused variable 'c' [-Wunused-variable]
             int pos = v, c = 0;
                          ^
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], &b[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 0 / 43