Submission #564963

#	Time	Username	Problem	Language	Result	Execution time	Memory
564963		Rifal	Building Skyscrapers (CEOI19_skyscrapers)	C++14	54 / 100	444 ms	41440 KiB

skyscrapers

#include <bits/stdc++.h>
#include <fstream>
#define endl '\n'
#define mod 32768
#define INF 100000000000000
//#define ll long long
//#define cin fin
//#define cout fout
using namespace std;
//ofstream fout("convention.out");
//ifstream fin("convention.in");
int main()
{
    ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
    int n, t;
    cin >> n >> t;
    map<pair<long long,long long>,long long> mp;
    long long cnt = 1;
    bool check[n+1] = {};
    vector<int> ans;
    priority_queue<pair<long long,long long>> pq;
    for(int i = 0; i < n; i++)
    {
        long long a, b;
        cin >> a >> b;
        if(i == 0)
        {
            pq.push({a,b});
        }
        mp[{a,b}] = cnt;
        cnt++;
    }
    while(!pq.empty())
    {
        pair<long long ,long long> tp = pq.top();
        long long x = tp.first, y = tp.second;
        ans.push_back(mp[{x,y}]);
        check[mp[{x,y}]] = 1;
        pq.pop();
        if(mp[{x+1,y}] > 0 && check[mp[{x+1,y}]] == 0)
        {
            pq.push({x+1,y});
            check[mp[{x+1,y}]] = 1;
        }
        if(mp[{x-1,y}] > 0 && check[mp[{x-1,y}]] == 0)
        {
            pq.push({x-1,y});
            check[mp[{x-1,y}]] = 1;
        }
        if(mp[{x,y+1}] > 0 && check[mp[{x,y+1}]] == 0)
        {
            pq.push({x,y+1});
            check[mp[{x,y+1}]] = 1;
        }
        if(mp[{x,y-1}] > 0 && check[mp[{x,y-1}]] == 0)
        {
            pq.push({x,y-1});
            check[mp[{x,y-1}]] = 1;
        }


        if(mp[{x+1,y+1}] > 0 && check[mp[{x+1,y+1}]] == 0)
        {
            pq.push({x+1,y+1});
            check[mp[{x+1,y+1}]] = 1;
        }
        if(mp[{x-1,y-1}] > 0 && check[mp[{x-1,y-1}]] == 0)
        {
            pq.push({x-1,y-1});
            check[mp[{x-1,y-1}]] = 1;
        }
        if(mp[{x-1,y+1}] > 0 && check[mp[{x-1,y+1}]] == 0)
        {
            pq.push({x-1,y+1});
            check[mp[{x-1,y+1}]] = 1;
        }
        if(mp[{x+1,y-1}] > 0 && check[mp[{x+1,y-1}]] == 0)
        {
            pq.push({x+1,y-1});
            check[mp[{x+1,y-1}]] = 1;
        }
    }
    bool ok = true;
    for(int i = 1; i <= n; i++)
    {
        if(check[i] == 0)
        {
            ok = false;
            break;
        }
    }
    if(ok)
    {
        cout << "YES" << endl;
        for(int i = 0; i < ans.size(); i++)
            cout << ans[i] << endl;
        return 0;
    }
    cout << "NO" << endl;
    return 0;
}

Compilation message (stderr)

skyscrapers.cpp: In function 'int main()':
skyscrapers.cpp:95:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |         for(int 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