Submission #1169668

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169668		pinruei	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	57 / 100	648 ms	300452 KiB

skyscraper

#pragma region//         
#include<bits/stdc++.h>
//#define int long long
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma comment(linker, "/stack:200000000")
#define f2(i, m) for(int i=0; i<m; i++)
#define f21(i, m) for(int i=1; i<m; i++)
#define f3(i, n, m) for(int i=n; i<m; i++)
#define f2_(i, m) for(int i=m; i>-1; i--)
#define f21_(i, m) for(int i=m; i>0; i--)
#define f3_(i, n, m) for(int i=n; i>=m; i--)
#define travG(idx) for(int i : g[idx])
#define travG_(i, idx) for(int i : g[idx])
#define trav(loop) for(int i : loop)
#define trav_(i, loop) for(int i : loop)
#define trav2(loop, idx) for(int i : loop[idx])
#define trav2_(i, loop, idx) for(int i : loop[idx])
#define ll long long
#define bs bitset
#define pii pair<int, int>
#define vi vector<int>
#define vvi vector<vector<int>>
#define ve vector<element>
#define ve_ vector<element_>
#define vpii vector<pair<int, int>>
#define qi queue<int>
#define qe queue<element>
#define qpii queue<pair<int, int>>
#define si stack<int>
#define se stack<element>
#define spii stack<pair<int, int>>
#define vb vector<bool>
#define pqi priority_queue<int>
#define pqi_ priority_queue<int, vi, greater<int>>
#define pqpii priority_queue<pair<int, int>>
#define pqpii_ priority_queue<pair<int, int>, vpii, greater<pii>>
#define pb push_back
#define pf push_front
#define pob pop_back()
#define pof pop_front()
#define len length()
#define elif else if
#define mod 1000000007
#pragma endregion
//#define debug
/*
#ifdef debug
#endif
#ifndef debug
#endif
*/
using namespace std;
using vvpib = vector<vector<pair<int, bool>>>;
using vpib = vector<pair<int, bool>>;
using pib = pair<int, bool>;
 
constexpr bool debug = 0;
int n, m;
 
signed main()//         https://tioj.ck.tp.edu.tw/problems/2363
{   ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    /*
    pii input[m];
    f2(i, m) cin>>input[i].first>>input[i].second;
    int srt=input[0].first, stp=input[1].first;
    sort(input, input+m, [](pii a, pii b)
    {
        return (pii){a.second, a.first%a.second} < (pii){b.second, b.first%b.second};
    });*/
 
    auto cmp = [](const pii a, const pii b)
    {
        return (pii){a.second, a.first%a.second} > (pii){b.second, b.first%b.second};
    };
    priority_queue<pii, vpii, decltype(cmp)> input(cmp);
    int tmp[n], pre=0, pre_=0;
    vvi g(n);
    int idx = n;// maintain g.size()
    int a, b;
    cin>>a>>b;
    int srt=a;
    input.push({a, b});
    cin>>a>>b;
    int stp=a;
    input.push({a, b});
    f2(i, m-2)
    {
        cin>>a>>b;
        input.push({a, b});
    }
 
    /*
    if constexpr(debug)
    {
        cout << srt << ' ' << stp << '\n';
        while(!input.empty())
        {
            pii i = input.top(); input.pop();
            cout << i.first << ' ' << i.second << '\n';
        }
    }*/
 
    //for(pii &i : input)
    while(!input.empty())
    {
        pii i = input.top(); input.pop();
        //cout << i.first << ' ' << i.second << "    ";
        if(i.second!=pre || i.first%i.second!=pre_)
        {
            bool flag=0;
            for(int j=i.first%i.second; j<n; j+=i.second, flag=1, idx++)
            {
                g.pb({j});
                tmp[j]=idx;
                #ifndef debug
                //cout<<idx<<' '<<j<<' '<<0<<'\n';
                #endif
                if(flag)
                {
                    g[idx-1].pb(idx), g[idx].pb(idx-1);
                    #ifndef debug
                    //cout<<idx<<' '<<idx-1<<' '<<1<<'\n';
                    //cout<<idx-1<<' '<<idx<<' '<<1<<'\n';
                    #endif
                }
            }
            pre=i.second, pre_=i.first%i.second;
        }
        g[i.first].pb(tmp[i.first]);
        #ifndef debug
        //cout<<i.first<<' '<<tmp[i.first]<<' '<<0<<'\n';
        #endif
    }
 
    // 01BFS
    // to fix
    int vis[idx];
    fill(vis, vis+idx, INT_MAX);
    
    deque<int> dq;
    dq.pb(srt);
    vis[srt]=0;
    while(!dq.empty())
    {
        int now = dq.front(); dq.pop_front();
        for(int &i : g[now])
        {
            bool jump = now>=n&&i>=n;
            if(vis[i]<=vis[now]+jump) continue;
            vis[i]=vis[now]+jump;
            if(jump) dq.pb(i);
            else dq.pf(i);
        }
        if(vis[stp]!=INT_MAX)
        {
            cout << vis[stp];
            return 0;
        }
    }
    
    //cout << vis[stp];
    //deque<pii> dq; dq.pb({srt, 0});
    /*
    si q[2]; q[0].push(srt);
    int ans = 0;
    while(!q[0].empty()||!q[1].empty())
    {
        si &nxt=q[(ans&1)^1];
        while(!q[ans&1].empty())
        {
            int now=q[ans&1].top(); q[ans&1].pop();
            //cout << '\n' << now << ' ';
            for(int &i : g[now])
            {
                //cout << ' ' << i;
                bool jump = now>=n&&i>=n;
                if(vis[i]<=ans+jump) continue;
                vis[i]=ans+jump;
                if(jump) nxt.push(i);
                else q[ans&1].push(i);
            }
            if(vis[stp]!=1e9)
            {
                cout << vis[stp];
                return 0;
            }
        }
        ans++;
        //cout << "          " << ans;
    }
    */



    /*while(!dq.empty())
    {
        pii now = dq.front(); dq.pop_front();
        //cout << '\n' << now.first << ' ';
        for(int &i : g[now.first])
        {
            //cout<<' '<<i;
            if(vis[i]&&i>=n) continue;
            vis[i]=1;
            if(i==stp)
            {
                cout << now.second+(now.first>=n&&i>=n);
                return 0;
            }
            if(now.first>=n&&i>=n) dq.pb({i, now.second+1});
            else dq.pf({i, now.second});
        }
    }*/
    cout << -1;
    return 0;
}

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