Submission #533197

#	Time	Username	Problem	Language	Result	Execution time	Memory
533197		wenqi	Building Skyscrapers (CEOI19_skyscrapers)	C++17	34 / 100	67 ms	8388 KiB

skyscrapers

// trans rights

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define M 1000000069

int N, T;
int X[150069];
int Y[150069];
unordered_map<ll, int> P;

int main(int argc, const char *argv[])
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> T;
    priority_queue<pair<int, int>> pq;
    for (int i = 1; i <= N; i++)
    {
        int x, y;
        cin >> x >> y;
        X[i] = x;
        Y[i] = y;

        if (i == 1)
        {
            pq.push({0, i});
        }else{
            P[(ll) x * M + y] = i;
        }
    }
    vector<int> R;
    while (not pq.empty())
    {
        int i = pq.top().second;
        pq.pop();

        R.push_back(i);

        for (int x = -1; x <= 1; x++)
        {
            for (int y = -1; y <= 1; y++)
            {
                ll idx = (ll) (X[i] + x) * M + (Y[i] + y);
                if (P[idx])
                {
                    int j = P[idx];
                    pq.push({-abs(X[j] - X[1]) -abs(Y[j] - Y[1]), j});
                    P[idx] = 0;
                }
            }
        }
    }
    if (R.size() != N)
    {
        cout << "NO\n";
    }else{
        cout << "YES\n";

        for (int a : R)
            cout << a << '\n';
    }
    return 0;
}

Compilation message (stderr)

skyscrapers.cpp: In function 'int main(int, const char**)':
skyscrapers.cpp:57:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   57 |     if (R.size() != N)
      |         ~~~~~~~~~^~~~

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 12 / 12
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20
• Subtask 6: 0 / 10
• Subtask 7: 0 / 19