Submission #1143058

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143058		solstice	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	10 / 100	1 ms	328 KiB

skyscraper

// solstice 
// created at 30 january 2025 
// sussy baka
/*
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠠⠖⠀⠀⢀⣨⣤⡤⠶⠶⠶⠶⢦⣤⣤⣀⠐⠢⢤⣀⠀⠀⠀⠀⠀⠀⠀⡆⣿⠀⠀⣀⠈⢷⡘⣷⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⡴⠚⠉⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠉⠓⠦⣌⡙⠶⣄⠀⠀⠀⢠⠀⣿⠀⢠⡇⠀⠈⡇⢸⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⠶⠋⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠷⣌⠻⣦⣠⠏⣸⠃⢀⣎⡇⠀⢠⡇⣼⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⠞⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡀⢀⡴⠶⣄⠀⠀⠀⠀⠈⠳⣌⡙⢰⠇⢀⣾⠟⠛⢳⡼⢁⠋⠀⠀⠀⠀⠀
⠀⠰⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣾⡏⠀⠀⠀⠓⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢿⠙⠻⢤⣀⣈⣷⡚⠛⠲⠦⣄⣨⣿⡟⢠⡿⠁⢀⣴⠟⢡⠎⠀⠀⠀⠀⠀⠀
⠀⠀⠹⡏⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⠞⠋⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣼⣧⡀⠀⠀⠀⠉⠉⠳⣄⠀⠈⠙⣿⢁⣿⣥⣶⡟⢁⣠⡤⠔⠒⠒⠒⠒⠀⠀
⠀⠀⠀⢻⣦⡀⣀⡀⠀⠀⠀⠀⠀⣠⡴⠛⠉⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣴⣿⣏⡁⢎⠻⠶⣦⣄⠀⠀⠀⠈⣧⠀⠀⣿⣼⡿⣿⣿⠟⠋⢁⣀⠀⠀⠀⠀⠀⠀⣀
⠀⠀⠀⠀⢿⡁⠉⠉⠉⠁⢀⣴⠞⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣴⣟⣛⡛⠉⣿⡻⢷⣶⣾⡶⣿⢷⡄⠀⠀⢸⡷⣦⣸⣿⣿⣶⣿⣶⣾⣿⣦⠀⢀⣀⡤⠖⠋⠁
⠀⠀⠀⠀⠈⢷⡀⠀⠀⢠⣿⡅⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣴⣾⣿⣿⣿⣿⣿⣶⣿⣷⣄⠙⢯⡉⠙⠛⠛⢦⣄⡋⢛⠀⢻⠋⣠⡟⢸⣿⣋⣀⣼⣶⡟⢥⡖⠋⠁⠀
⠀⠀⠀⠀⠀⠈⡇⠀⠀⣿⠋⢻⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣴⡾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⡀⠙⠒⠒⠒⠂⠻⣿⣺⠀⣼⠟⠉⢀⣼⣿⣿⣿⣿⣙⢿⡌⢷⡀⠀⠀
⠀⠀⠀⠀⠀⠀⣇⠀⠀⢸⣦⣌⣻⣷⣤⣄⣀⠀⠀⣀⣤⣶⣾⣿⣿⣿⣶⣿⣿⣿⣿⣿⣿⣿⣽⣿⣿⣏⣹⣿⣦⡀⠀⢀⣤⡴⠛⢿⡞⠃⠀⢠⣾⣧⣅⡀⠸⣿⣿⣾⢳⡄⢳⣄⠀
⠀⠀⠀⠀⠀⠀⠙⠷⣤⣄⣉⠻⠿⣶⣤⣭⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠇⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣾⣿⠏⢀⡴⠿⠿⢶⣾⣋⠁⠀⠈⢳⣄⣿⣿⣿⣧⣿⡆⢸⢠
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢨⡿⣠⣿ ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠀⠈⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⢁⡴⠛⠃⣀⠀⠀⠙⡇⢀⣀⣀⣈⣿⣿⣿⣿⣿⣿⠇⣼⣻
⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⠞⢰⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠗⠶⠦⢼⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣶⣾⣿⣿⣿⣿⣿⣷⣤⣿⣿⣿⣿⣿⣿⣿⣿⣿⠟⢁⡼⣹⣿
⣤⣤⡀⠀⠀⢀⣤⣴⠞⠋⠀⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡏⠀⠀⠀⠀⠺⣻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠋⠁⠀⠈⣸⣿⣿
⣿⣿⣿⣷⠞⢉⡽⠁⠀⠀⢰⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⣿⣿⣿⠏⠀⢀⣠⣤⣤⣀⠉⢪⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡅⠀⠀⠀⠀⣿⣿⣿
⣿⠿⠋⠀⢀⠞⠀⠀⠀⢠⣾⣿⣿⣿⣿⣿⣿⠟⣹⣥⡀⣰⣿⡿⠁⠀⠀⢩⣾⣿⣿⡙⠿⣦⣍⠈⠛⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⠀⠀⠀⠀⢻⡿⢸
⠀⠀⠀⢠⠏⠀⠠⠤⠾⠿⠛⣿⣿⣿⣿⣿⣿⣰⣟⣿⣾⠟⠉⠀⠀⠀⠀⠀⣿⣟⣿⡟⠓⠺⢿⣿⠦⠞⣿⣿⣿⣿⣿⣿⣿⡟⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠃⠀⠀⠀⠀⠈⠃⠘
⠀⠀⢠⠏⠀⠀⠀⣠⠶⠆⢸⡿⢻⣿⣿⣿⣿⣿⡟⣿⣟⠀⠀⠀⠀⠀⠀⠀⠹⣿⣻⡟⣀⡀⠚⠁⠀⠀⣿⣿⣿⣿⣿⣿⣯⣤⡈⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⠀⢀⣀⠀
⠀⢠⠏⠀⠀⣠⠞⠁⠀⠀⢸⡇⠀⢻⣿⣿⣿⣧⠁⣻⣿⣷⠀⠀⠀⠀⠀⠀⠀⠈⠉⠉⠉⠀⠀⠀⠀⢀⣿⠃⢹⣿⣿⣿⣡⣾⡇⢸⣿⣿⣿⣿⣿⣿⣿⡿⣿⣧⡀⠀⠀⠀⣾⣿⣿
⢀⠏⢀⡠⠞⠉⠀⠀⠀⠀⠘⠃⠁⢸⣿⣿⣿⣿⠀⠉⣹⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡾⣁⢠⣾⣿⣿⣿⣿⠛⣰⣿⣿⣿⣿⣿⣿⣿⣿⠁⠈⠉⠛⠒⢀⣴⣿⣿⣿
⢞⠀⠈⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣿⣿⣿⣿⠀⠈⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠚⣱⣿⣿⣿⣿⣿⣿⣾⣿⣿⣿⣿⣿⣿⠟⣿⠁⠀⠀⠀⠀⠁⣸⣿⣿⣿⣿
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡾⠿⠛⣿⣿⣿⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣰⠟⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢃⣤⣘⠇⠀⠀⣰⣿⣿⣿⣿⣿⣿⣿
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠹⣿⣿⣿⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡴⠋⠀⠹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⢸⣿⠙⠛⠛⠻⠛⣀⣽⡿⣿⢿⣿⠿
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣿⣿⣿⠙⢧⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣤⠟⠀⠀⣠⣾⣿⣿⣿⡟⠙⣿⣿⣿⠻⣿⣷⠸⠿⠶⠶⠶⣦⣄⠁⠂⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣿⡟⣿⣿⣧⠀⠻⣄⠀⠀⠀⠀⠀⠀⠀⢀⣠⡴⠏⠁⠀⠀⢀⢿⣿⣿⣿⣿⠇⠀⢹⣿⢿⣶⣾⣿⡶⠖⠒⠒⠲⣆⢻⣆⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣿⣿⣿⠁⠀⠀⠘⣦⡀⠀⢀⣀⣴⣾⠿⣅⠀⠀⠀⠀⠀⠀⣸⣿⣿⣟⠁⢀⣀⣠⣿⡿⠟⠋⠁⠀⠀⠀⠀⠀⠹⣆⠻⣦⡀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣴⠟⢻⣿⢻⡄⠀⠀⠀⠈⣙⣛⣻⣭⣴⠶⡛⢿⡆⠀⠀⠀⢀⣼⡿⢿⣿⣿⣟⣿⡿⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠳⣬⡙⠂⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣧⣸⣧⣿⡥⠖⠒⠋⠉⠉⣡⣾⠏⣡⣤⣯⣿⣿⣤⣶⣾⡿⣿⣿⣞⣿⣿⣿⠏⠀⠀⠀⢀⣀⣀⣀⣀⣀⣀⣀⣀⣀⣀⣀⡈⠙⠓⠲⢦⠀
⠀⠀⠀⠀⠀⠀⠀⠘⠶⣶⢤⠤⠤⠤⣶⣾⢿⣿⡇⠀⠀⠀⠀⢀⣾⠟⠀⠀⣿⣿⠿⢿⡿⠚⠋⢹⠀⣿⡇⣿⡟⢉⣟⣠⣤⣶⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣯⣭⣉⣀⠀⠈⢠
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠙⠓⠲⠾⢿⣀⣼⣿⠧⣶⣶⣶⣿⣿⣿⡀⠀⢠⣿⡏⠀⢸⡇⠀⠀⢸⡆⢻⣿⣿⣷⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡷⠆⣼
⠀⠀⠀⠀⠀⠀⠀⠀⢀⠀⠀⠀⣠⣄⡀⣹⠟⣠⡾⠛⣻⣿⣿⣿⣿⣿⣀⣼⠏⠀⠀⣾⠀⠀⠀⢸⣇⣼⣿⣿⣯⠄⡌⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣾⣿⣿⣿⣿⡿⣿⠃⣼⣿
⠀⠀⠀⠀⠀⠀⠀⠀⠸⣧⣀⣠⣿⡙⣛⣿⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡏⠀⠀⣼⣧⣤⣶⣿⣿⣿⣿⣿⣿⡇⣀⣰⣞⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠃⣸⣿⣿
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define vi vector<int>
#define vl vector<ll>
#define vb vector<bool>
#define vvi vector<vector<int>>
#define vvl vector<vector<ll>>
#define el '\n'
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define all(v) v.begin(), v.end()

template<class T> using pq = priority_queue<T>;
template<class T> bool ckmin(T& a,const T& b) {return b<a ? a=b,1:0;}
template<class T> bool ckmax(T& a,const T& b) {return a<b ? a=b,1:0;}

template<typename T, typename V> 
void __print(const pair<T, V> &x);
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}

#define sz(x) (int)(x).size()
#define lb lower_bound 
#define ub upper_bound

const int mod=1e9+7;
//const int mod=998244353;

struct state{
    int dodge,pos,jump;
    state(int d,int p,int j):dodge(d),pos(p),jump(j) {}
};

int sol(int n,int m,vi& b,vi& p){
    set<pii> vis;
    queue<state>q;
    q.push(state(0,b[0],0));
    vis.insert({0,b[0]});

    vb has(m,0);
    has[0]=0;

    while(!q.empty()){
        state cur=q.front();q.pop();
        if(has[1])return cur.jump;

        for(int i=0;i<m;i++){
            if(!has[i] and b[i]==cur.pos){
                has[i]=1;
                q.push(state(i,cur.pos,cur.jump));
                vis.insert({i,cur.pos});
            } 
        }
        int pp=p[cur.dodge];
         if(cur.pos+pp<n && !vis.count({cur.dodge,cur.pos+pp})){
            q.push(state(cur.dodge,cur.pos+pp, cur.jump+1));
            vis.insert({cur.dodge,cur.pos+pp});
        }
        if (cur.pos-pp>= 0 && !vis.count({cur.dodge,cur.pos-pp})) {
            q.push(state(cur.dodge,cur.pos-pp,cur.jump+1));
            vis.insert({cur.dodge,cur.pos-pp});
        }
    }
    return -1;
}

void solve() {
    int n,m;cin>>n>>m;
    vi b(m),p(m);
    for(int i=0;i<m;i++)cin>>b[i]>>p[i];
    cout<<sol(n,m,b,p)<<el;
}

int main(){
    cin.tie(0)->sync_with_stdio(0); 
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    solve();
    return 0;
}

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