Submission #914033

#	Time	Username	Problem	Language	Result	Execution time	Memory
914033		CyberCow	Building Skyscrapers (CEOI19_skyscrapers)	C++17	54 / 100	556 ms	32156 KiB

skyscrapers

#include <random>
#include <algorithm>
#include <bitset>
#include <chrono>
#include <cmath>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <chrono>
#define fr first
#define sc second
#define ad push_back
using namespace std;
using ll = long long;
mt19937 rnd(348502);

const ll N = 1010;

map<pair<int, int>, int> ma;
map<pair<int, int>, int> ogt;

void solve()
{
    int  n, i, j, x, y, t;
    cin >> n >> t;
    vector<pair<int, int>> v;
    set<pair<int, int>> s;
    for ( i = 0; i < n; i++)
    {
        cin >> x >> y;
        ma[{x, y}] = i + 1;
        s.insert({ x, y });
        v.push_back({ x, y });
    }
    int x1 = x, y1 = y;
    priority_queue<pair<int, pair<int, int>>> p;
    vector<int> ans;
    p.push({ 0, {x, y} });
    while (!p.empty())
    {
        x = p.top().second.first;
        y = p.top().second.second;
        ans.push_back(ma[{x, y}]);
        p.pop();
        ogt[{x, y}] = 1;
        for (i = -1; i <= 1; i++)
        {
            for (j = -1; j <= 1; j++)
            {
                if (s.find({ x + i, y + j }) != s.end() && ogt[{x + i, y + j}] == 0)
                {
                    p.push({-( abs(x1 - (x + i)) + abs((y1 - (y + j)))), {x + i, y + j} });
                    ogt[{x + i, y + j}] = 1;
                }
            }
        }
    }
    if (ans.size() == n)
    {
        cout << "YES\n";
        for ( i = 0; i < ans.size(); i++)
        {
            cout << ans[i] << '\n';
        }
    }
    else
    {
        cout << "NO\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll tt = 1;
    //cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}

Compilation message (stderr)

skyscrapers.cpp: In function 'void solve()':
skyscrapers.cpp:69:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   69 |     if (ans.size() == n)
      |         ~~~~~~~~~~~^~~~
skyscrapers.cpp:72:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         for ( i = 0; i < ans.size(); i++)
      |                      ~~^~~~~~~~~~~~

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