Submission #1245228

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245228		Mousa_Aboubaker	Building Skyscrapers (CEOI19_skyscrapers)	C++20	8 / 100	428 ms	10136 KiB

skyscrapers

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

template <typename T>
using pqg = priority_queue<T, vector<T>, greater<T>>;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    int t;
    cin >> t;
    vector<pair<int, int>> a(n);
    for(auto &[f, s]: a)
        cin >> f >> s;
    map<pair<int, int>, int> mp;
    vector<bool> vis(n, false);
    for(int i = 0; i < n; i++)
    {
        auto [x, y] = a[i];
        mp[{x, y}] = i;
    }
    vector<int> cnt(n, 0);
    auto get = [&](int x, int y) -> int
    {
        if(mp.find({x, y}) == mp.end())
            return -1;
        int i = mp[{x, y}];
        return i;
    };
    for(int i= 0; i < n; i++)
    {
        auto [x, y] = a[i];
        for(int j = x - 1; j <= x + 1; j++)
            for(int k = y - 1; k <= y + 1; k++)
            {
                int d = get(j, k);
                if(d == -1)
                    continue;
                cnt[i]++;
            }
    }
    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int l, int r)
    {
        if(cnt[l] == cnt[r])
            return a[l].first < a[r].first;
        return cnt[l] > cnt[r];
    });
    priority_queue<tuple<int, int, int, int>> q;
    q.push({cnt[ord[0]], ord[0], a[ord[0]].first, a[ord[0]].second});
    vector<int> res;
    while(!q.empty())
    {
        auto [cost, i, x, y]= q.top();
        q.pop();

        if(vis[i])
            continue;
        res.push_back(i);
        vis[i] = true;
        for(int j = x - 1; j <= x + 1; j++)
            for(int k = y - 1; k <= y + 1; k++)
            {
                int d = get(j, k);
                if(d == -1)
                    continue;
                q.push({cnt[d], d, j, k});
            }
    }

    // for(int i = 0; i < n; i++)
    //     cout << vis[i] << ' ';
    // cout << '\n';

    bool can = count(vis.begin(), vis.end(), true) == n;
    if(!can)
    {
        cout << "NO";
        return 0;
    }

    // shuffle(res.begin(), res.end(), rng);

    cout << "YES\n";
    for(auto i: res)
        cout << i + 1 << '\n';
}

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