Submission #709920

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
709920	2023-03-14T19:36:03 Z	noedit	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	Compilation error	0 ms	0 KB

skyscraper

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

using namespace std;

typedef long long ll;

const int INF = 1e9;
int B = 500;
const int MAXN = 3e4 + 5;

vector<pair<int, int> > d;

int dist[MAXN][B];
vector<short> sm[MAXN];
vector<short> bg[MAXN];

signed main()
{
    //ifstream cin("input.txt");
    //ofstream cout("output.txt");
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    B = (int)sqrt(n);
    d.resize(m);
    vector<int> big;
    for (int i = 0; i < m; i++)
    {
        cin >> d[i].first >> d[i].second;
        if (d[i].second >= B)
        {
            big.push_back(i);
            bg[d[i].first].push_back(d[i].second);
        }
        else
        {
            sm[d[i].first].push_back(d[i].second);
        }
    }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < B; j++)
            dist[i][j] = INF;
    priority_queue<array<int, 3> > st;
    st.push({0, d[0].first, 0});
    dist[d[0].first][0] = 0;
    while (!st.empty())
    {
        auto [dst, pos, pw] = st.top();
        dst = -dst;
        st.pop();
        if (dst > dist[pos][pw]) continue;
        if (dst != dist[pos][pw]) continue;
        if (pw > 0)
        {
            vector<array<short, 3> > to;
            if (pos - pw >= 0)
            {
                if (dist[pos - pw][pw] > dst + 1)
                {
                    //st.erase({dist[pos - pw][pw], pos - pw, pw});
                    dist[pos - pw][pw] = dst + 1;
                    st.push({-dist[pos - pw][pw], pos - pw, pw});
                }
                if (dist[pos - pw][0] > dst + 1)
                {
                    //st.erase({dist[pos - pw][0], pos - pw, 0});
                    dist[pos - pw][0] = dst + 1;
                    st.push({-dist[pos - pw][0], pos - pw, 0});
                }
            }
            if (pos + pw < n)
            {
                if (dist[pos + pw][pw] > dst + 1)
                {
                    //st.erase({dist[pos + pw][pw], pos + pw, pw});
                    dist[pos + pw][pw] = dst + 1;
                    st.push({-dist[pos + pw][pw], pos + pw, pw});
                }
                if (dist[pos + pw][0] > dst + 1)
                {
                    //st.erase({dist[pos + pw][0], pos + pw, 0});
                    dist[pos + pw][0] = dst + 1;
                    st.push({-dist[pos + pw][0], pos + pw, 0});
                }
            }
            continue;
        }
        for (auto& mv : bg[pos])
        {
            for (int j = pos, k = 0; j < n; j += mv, k++)
            {
                if (dist[j][0] > dst + k)
                {
                    dist[j][0] = dst + k;
                    st.push({-dist[j][0], j, 0});
                }
            }
            for (int j = pos, k = 0; j >= 0; j -= mv, k++)
            {
                if (dist[j][0] > dst + k)
                {
                    dist[j][0] = dst + k;
                    st.push({-dist[j][0], j, 0});
                }
            }
        }
        for (auto& mv : sm[pos])
        {
            if (dist[pos][mv] > dst + 0)
            {
                dist[pos][mv] = dst + 0;
                st.push({-dist[pos][mv], pos, mv});
            }
        }
    }
    int mn = INF;
    for (int i = 0; i < B; i++)
        mn = min(mn, dist[d[1].first][i]);
    if (mn == INF)
        cout << -1;
    else
        cout << mn;
    return 0;
}
/*
small
(i, j) -1> (i - j, 0), (i + j, 0)
(i, 0) -0> (i, j)
(i, j) -1> (i - j, j), (i + j, j)
large
(i, 0) -1> (i + j, 0)
(i, 0) -1> (i - j, 0)
*/

Compilation message

skyscraper.cpp:15:17: error: array bound is not an integer constant before ']' token
   15 | int dist[MAXN][B];
      |                 ^
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:46:13: error: 'dist' was not declared in this scope
   46 |             dist[i][j] = INF;
      |             ^~~~
skyscraper.cpp:49:5: error: 'dist' was not declared in this scope; did you mean 'st'?
   49 |     dist[d[0].first][0] = 0;
      |     ^~~~
      |     st
skyscraper.cpp:66:64: error: no matching function for call to 'std::priority_queue<std::array<int, 3> >::push(<brace-enclosed initializer list>)'
   66 |                     st.push({-dist[pos - pw][pw], pos - pw, pw});
      |                                                                ^
In file included from /usr/include/c++/10/queue:64,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
                 from skyscraper.cpp:1:
/usr/include/c++/10/bits/stl_queue.h:640:7: note: candidate: 'void std::priority_queue<_Tp, _Sequence, _Compare>::push(const value_type&) [with _Tp = std::array<int, 3>; _Sequence = std::vector<std::array<int, 3>, std::allocator<std::array<int, 3> > >; _Compare = std::less<std::array<int, 3> >; std::priority_queue<_Tp, _Sequence, _Compare>::value_type = std::array<int, 3>]'
  640 |       push(const value_type& __x)
      |       ^~~~
/usr/include/c++/10/bits/stl_queue.h:640:30: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type&' {aka 'const std::array<int, 3>&'}
  640 |       push(const value_type& __x)
      |            ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_queue.h:648:7: note: candidate: 'void std::priority_queue<_Tp, _Sequence, _Compare>::push(std::priority_queue<_Tp, _Sequence, _Compare>::value_type&&) [with _Tp = std::array<int, 3>; _Sequence = std::vector<std::array<int, 3>, std::allocator<std::array<int, 3> > >; _Compare = std::less<std::array<int, 3> >; std::priority_queue<_Tp, _Sequence, _Compare>::value_type = std::array<int, 3>]'
  648 |       push(value_type&& __x)
      |       ^~~~
/usr/include/c++/10/bits/stl_queue.h:648:25: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::priority_queue<std::array<int, 3> >::value_type&&' {aka 'std::array<int, 3>&&'}
  648 |       push(value_type&& __x)
      |            ~~~~~~~~~~~~~^~~
skyscraper.cpp:72:62: error: no matching function for call to 'std::priority_queue<std::array<int, 3> >::push(<brace-enclosed initializer list>)'
   72 |                     st.push({-dist[pos - pw][0], pos - pw, 0});
      |                                                              ^
In file included from /usr/include/c++/10/queue:64,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
                 from skyscraper.cpp:1:
/usr/include/c++/10/bits/stl_queue.h:640:7: note: candidate: 'void std::priority_queue<_Tp, _Sequence, _Compare>::push(const value_type&) [with _Tp = std::array<int, 3>; _Sequence = std::vector<std::array<int, 3>, std::allocator<std::array<int, 3> > >; _Compare = std::less<std::array<int, 3> >; std::priority_queue<_Tp, _Sequence, _Compare>::value_type = std::array<int, 3>]'
  640 |       push(const value_type& __x)
      |       ^~~~
/usr/include/c++/10/bits/stl_queue.h:640:30: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type&' {aka 'const std::array<int, 3>&'}
  640 |       push(const value_type& __x)
      |            ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_queue.h:648:7: note: candidate: 'void std::priority_queue<_Tp, _Sequence, _Compare>::push(std::priority_queue<_Tp, _Sequence, _Compare>::value_type&&) [with _Tp = std::array<int, 3>; _Sequence = std::vector<std::array<int, 3>, std::allocator<std::array<int, 3> > >; _Compare = std::less<std::array<int, 3> >; std::priority_queue<_Tp, _Sequence, _Compare>::value_type = std::array<int, 3>]'
  648 |       push(value_type&& __x)
      |       ^~~~
/usr/include/c++/10/bits/stl_queue.h:648:25: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::priority_queue<std::array<int, 3> >::value_type&&' {aka 'std::array<int, 3>&&'}
  648 |       push(value_type&& __x)
      |            ~~~~~~~~~~~~~^~~
skyscraper.cpp:81:64: error: no matching function for call to 'std::priority_queue<std::array<int, 3> >::push(<brace-enclosed initializer list>)'
   81 |                     st.push({-dist[pos + pw][pw], pos + pw, pw});
      |                                                                ^
In file included from /usr/include/c++/10/queue:64,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
                 from skyscraper.cpp:1:
/usr/include/c++/10/bits/stl_queue.h:640:7: note: candidate: 'void std::priority_queue<_Tp, _Sequence, _Compare>::push(const value_type&) [with _Tp = std::array<int, 3>; _Sequence = std::vector<std::array<int, 3>, std::allocator<std::array<int, 3> > >; _Compare = std::less<std::array<int, 3> >; std::priority_queue<_Tp, _Sequence, _Compare>::value_type = std::array<int, 3>]'
  640 |       push(const value_type& __x)
      |       ^~~~
/usr/include/c++/10/bits/stl_queue.h:640:30: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type&' {aka 'const std::array<int, 3>&'}
  640 |       push(const value_type& __x)
      |            ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_queue.h:648:7: note: candidate: 'void std::priority_queue<_Tp, _Sequence, _Compare>::push(std::priority_queue<_Tp, _Sequence, _Compare>::value_type&&) [with _Tp = std::array<int, 3>; _Sequence = std::vector<std::array<int, 3>, std::allocator<std::array<int, 3> > >; _Compare = std::less<std::array<int, 3> >; std::priority_queue<_Tp, _Sequence, _Compare>::value_type = std::array<int, 3>]'
  648 |       push(value_type&& __x)
      |       ^~~~
/usr/include/c++/10/bits/stl_queue.h:648:25: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::priority_queue<std::array<int, 3> >::value_type&&' {aka 'std::array<int, 3>&&'}
  648 |       push(value_type&& __x)
      |            ~~~~~~~~~~~~~^~~
skyscraper.cpp:87:62: error: no matching function for call to 'std::priority_queue<std::array<int, 3> >::push(<brace-enclosed initializer list>)'
   87 |                     st.push({-dist[pos + pw][0], pos + pw, 0});
      |                                                              ^
In file included from /usr/include/c++/10/queue:64,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
                 from skyscraper.cpp:1:
/usr/include/c++/10/bits/stl_queue.h:640:7: note: candidate: 'void std::priority_queue<_Tp, _Sequence, _Compare>::push(const value_type&) [with _Tp = std::array<int, 3>; _Sequence = std::vector<std::array<int, 3>, std::allocator<std::array<int, 3> > >; _Compare = std::less<std::array<int, 3> >; std::priority_queue<_Tp, _Sequence, _Compare>::value_type = std::array<int, 3>]'
  640 |       push(const value_type& __x)
      |       ^~~~
/usr/include/c++/10/bits/stl_queue.h:640:30: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type&' {aka 'const std::array<int, 3>&'}
  640 |       push(const value_type& __x)
      |            ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_queue.h:648:7: note: candidate: 'void std::priority_queue<_Tp, _Sequence, _Compare>::push(std::priority_queue<_Tp, _Sequence, _Compare>::value_type&&) [with _Tp = std::array<int, 3>; _Sequence = std::vector<std::array<int, 3>, std::allocator<std::array<int, 3> > >; _Compare = std::less<std::array<int, 3> >; std::priority_queue<_Tp, _Sequence, _Compare>::value_type = std::array<int, 3>]'
  648 |       push(value_type&& __x)
      |       ^~~~
/usr/include/c++/10/bits/stl_queue.h:648:25: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::priority_queue<std::array<int, 3> >::value_type&&' {aka 'std::array<int, 3>&&'}
  648 |       push(value_type&& __x)
      |            ~~~~~~~~~~~~~^~~
skyscraper.cpp:99:48: error: no matching function for call to 'std::priority_queue<std::array<int, 3> >::push(<brace-enclosed initializer list>)'
   99 |                     st.push({-dist[j][0], j, 0});
      |                                                ^
In file included from /usr/include/c++/10/queue:64,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
                 from skyscraper.cpp:1:
/usr/include/c++/10/bits/stl_queue.h:640:7: note: candidate: 'void std::priority_queue<_Tp, _Sequence, _Compare>::push(const value_type&) [with _Tp = std::array<int, 3>; _Sequence = std::vector<std::array<int, 3>, std::allocator<std::array<int, 3> > >; _Compare = std::less<std::array<int, 3> >; std::priority_queue<_Tp, _Sequence, _Compare>::value_type = std::array<int, 3>]'
  640 |       push(const value_type& __x)
      |       ^~~~
/usr/include/c++/10/bits/stl_queue.h:640:30: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type&' {aka 'const std::array<int, 3>&'}
  640 |       push(const value_type& __x)
      |            ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_queue.h:648:7: note: candidate: 'void std::priority_queue<_Tp, _Sequence, _Compare>::push(std::priority_queue<_Tp, _Sequence, _Compare>::value_type&&) [with _Tp = std::array<int, 3>; _Sequence = std::vector<std::array<int, 3>, std::allocator<std::array<int, 3> > >; _Compare = std::less<std::array<int, 3> >; std::priority_queue<_Tp, _Sequence, _Compare>::value_type = std::array<int, 3>]'
  648 |       push(value_type&& __x)
      |       ^~~~
/usr/include/c++/10/bits/stl_queue.h:648:25: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::priority_queue<std::array<int, 3> >::value_type&&' {aka 'std::array<int, 3>&&'}
  648 |       push(value_type&& __x)
      |            ~~~~~~~~~~~~~^~~
skyscraper.cpp:107:48: error: no matching function for call to 'std::priority_queue<std::array<int, 3> >::push(<brace-enclosed initializer list>)'
  107 |                     st.push({-dist[j][0], j, 0});
      |                                                ^
In file included from /usr/include/c++/10/queue:64,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
                 from skyscraper.cpp:1:
/usr/include/c++/10/bits/stl_queue.h:640:7: note: candidate: 'void std::priority_queue<_Tp, _Sequence, _Compare>::push(const value_type&) [with _Tp = std::array<int, 3>; _Sequence = std::vector<std::array<int, 3>, std::allocator<std::array<int, 3> > >; _Compare = std::less<std::array<int, 3> >; std::priority_queue<_Tp, _Sequence, _Compare>::value_type = std::array<int, 3>]'
  640 |       push(const value_type& __x)
      |       ^~~~
/usr/include/c++/10/bits/stl_queue.h:640:30: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type&' {aka 'const std::array<int, 3>&'}
  640 |       push(const value_type& __x)
      |            ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_queue.h:648:7: note: candidate: 'void std::priority_queue<_Tp, _Sequence, _Compare>::push(std::priority_queue<_Tp, _Sequence, _Compare>::value_type&&) [with _Tp = std::array<int, 3>; _Sequence = std::vector<std::array<int, 3>, std::allocator<std::array<int, 3> > >; _Compare = std::less<std::array<int, 3> >; std::priority_queue<_Tp, _Sequence, _Compare>::value_type = std::array<int, 3>]'
  648 |       push(value_type&& __x)
      |       ^~~~
/usr/include/c++/10/bits/stl_queue.h:648:25: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::priority_queue<std::array<int, 3> >::value_type&&' {aka 'std::array<int, 3>&&'}
  648 |       push(value_type&& __x)
      |            ~~~~~~~~~~~~~^~~
skyscraper.cpp:116:50: error: no matching function for call to 'std::priority_queue<std::array<int, 3> >::push(<brace-enclosed initializer list>)'
  116 |                 st.push({-dist[pos][mv], pos, mv});
      |                                                  ^
In file included from /usr/include/c++/10/queue:64,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
                 from skyscraper.cpp:1:
/usr/include/c++/10/bits/stl_queue.h:640:7: note: candidate: 'void std::priority_queue<_Tp, _Sequence, _Compare>::push(const value_type&) [with _Tp = std::array<int, 3>; _Sequence = std::vector<std::array<int, 3>, std::allocator<std::array<int, 3> > >; _Compare = std::less<std::array<int, 3> >; std::priority_queue<_Tp, _Sequence, _Compare>::value_type = std::array<int, 3>]'
  640 |       push(const value_type& __x)
      |       ^~~~
/usr/include/c++/10/bits/stl_queue.h:640:30: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type&' {aka 'const std::array<int, 3>&'}
  640 |       push(const value_type& __x)
      |            ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_queue.h:648:7: note: candidate: 'void std::priority_queue<_Tp, _Sequence, _Compare>::push(std::priority_queue<_Tp, _Sequence, _Compare>::value_type&&) [with _Tp = std::array<int, 3>; _Sequence = std::vector<std::array<int, 3>, std::allocator<std::array<int, 3> > >; _Compare = std::less<std::array<int, 3> >; std::priority_queue<_Tp, _Sequence, _Compare>::value_type = std::array<int, 3>]'
  648 |       push(value_type&& __x)
      |       ^~~~
/usr/include/c++/10/bits/stl_queue.h:648:25: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::priority_queue<std::array<int, 3> >::value_type&&' {aka 'std::array<int, 3>&&'}
  648 |       push(value_type&& __x)
      |            ~~~~~~~~~~~~~^~~