제출 #539060

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
539060		timreizin	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	308 ms	262144 KiB

skyscraper

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

using namespace std;

const int INF = 1e9;


int main()
{
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> doges(m);
    for (auto &[b, p] : doges) cin >> b >> p;
    const int D = 1000;
    vector<vector<int>> dp(n, vector<int>(D, 1e9));
    vector<vector<int>> 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(1e9);
    }
    auto getInd = [&canGet, &D](int v, int p)
    {
        if (p < D) return p;
        //assert(lower_bound(canGet[v].begin(), canGet[v].end(), p) != canGet[v].end());
        /*if (lower_bound(canGet[v].begin(), canGet[v].end(), p) == canGet[v].end())
        {
            cout << v << ' ' << p << '\n';
            exit(0);
        }*/
        return (int)distance(canGet[v].begin(), lower_bound(canGet[v].begin(), canGet[v].end(), p)) + D;
    };
    int ind = getInd(doges[0].first, doges[0].second);
    dp[doges[0].first][ind] = 0;
    deque<pair<int, int>> dq;
    dq.emplace_back(doges[0].first, doges[0].second);
    while (!dq.empty())
    {
        auto [i, p] = dq.front();
        dq.pop_front();
        int 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)
        {
            int 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)
        {
            int 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;
}

컴파일 시 표준 에러 (stderr) 메시지

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:32:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         for (int j = 0; j < canGet.size(); ++j) dp[i].push_back(1e9);
      |                         ~~^~~~~~~~~~~~~~~

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