Submission #539227

#	Time	Username	Problem	Language	Result	Execution time	Memory
539227		timreizin	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	22 / 100	2 ms	596 KiB

skyscraper

#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
#include <cassert>

using namespace std;

const short INF = 32767;


int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> doges(m);
    for (auto &[b, p] : doges) cin >> b >> p;
    const short D = 180;
    vector<vector<short>> dp(n, vector<short>(D, INF));
    vector<vector<short>> canGet(n), starts(n);
    for (auto &[b, p] : doges)
    {
        starts[b].push_back(p);
        if (p >= D) for (int i = b % p; i < n; i += p) canGet[i].push_back(p);
    }
    for (int i = 0; i < n; ++i)
    {
        sort(canGet[i].begin(), canGet[i].end());
        canGet[i].erase(unique(canGet[i].begin(), canGet[i].end()), canGet[i].end());
        sort(starts[i].begin(), starts[i].end());
        starts[i].erase(unique(starts[i].begin(), starts[i].end()), starts[i].end());
        //for (int j = 0; j < canGet.size(); ++j) dp[i].push_back(INF);
    }
    if (n <= 2000)
    {
    auto getInd = [&canGet, &D](short v, short p) -> short
    {
        if (p < D) return p;
        return (short)distance(canGet[v].begin(), lower_bound(canGet[v].begin(), canGet[v].end(), p)) + (short)D;
    };
    short ind = getInd(doges[0].first, doges[0].second);
    dp[doges[0].first][ind] = 0;
    deque<pair<short, short>> dq;
    dq.emplace_back(doges[0].first, doges[0].second);
    while (!dq.empty())
    {
        auto [i, p] = dq.front();
        dq.pop_front();
        short ind = getInd(i, p);
        for (int j : starts[i])
        {
            int ind2 = getInd(i, j);
            if (dp[i][ind2] > dp[i][ind])
            {
                dp[i][ind2] = dp[i][ind];
                dq.emplace_front(i, j);
            }
        }
        starts[i].clear();
        if (i - p >= 0)
        {
            short ind2 = getInd(i - p, p);
            if (dp[i - p][ind2] > dp[i][ind] + 1)
            {
                dp[i - p][ind2] = dp[i][ind] + 1;
                dq.emplace_back(i - p, p);
            }
        }
        if (i + p < n)
        {
            short ind2 = getInd(i + p, p);
            if (dp[i + p][ind2] > dp[i][ind] + 1)
            {
                dp[i + p][ind2] = dp[i][ind] + 1;
                dq.emplace_back(i + p, p);
            }
        }
    }
    ind = getInd(doges[1].first, doges[1].second);
    if (dp[doges[1].first][ind] == INF) cout << -1;
    else cout << dp[doges[1].first][ind];
    }
    return 0;
}
//47

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