Submission #564653

#	Time	Username	Problem	Language	Result	Execution time	Memory
564653		Rifal	Building Skyscrapers (CEOI19_skyscrapers)	C++14	0 / 100	142 ms	8504 KiB

skyscrapers

#include <bits/stdc++.h>
#include <fstream>
#define endl '\n'
#define mod 32768
#define INF 1000000000000000
#define ll long long
//#define cin fin
//#define cout fout
using namespace std;
const int M = 5e5;
 bool check[M] = {};
vector<pair<ll,ll>>v;
map<pair<ll,ll>,ll> mp;
vector<int> ans;
//ofstream fout("convention.out");
//ifstream fin("convention.in");
void doo(ll x, ll y)
{
    if(mp[{x-1,y}] > 0 && check[mp[{x-1,y}]] == 0)
    {
        check[mp[{x-1,y}]] = 1;
        ans.push_back(mp[{x-1,y}]);
        doo(x-1,y);
    }
    if(mp[{x+1,y}] > 0 && check[mp[{x+1,y}]] == 0)
    {
           check[mp[{x+1,y}]] = 1;
           ans.push_back(mp[{x+1,y}]);
           doo(x+1,y);
    }
    if(mp[{x,y-1}] > 0 && check[mp[{x,y-1}]] == 0)
    {
        check[mp[{x,y-1}]] = 1;
        ans.push_back(mp[{x,y-1}]);
        doo(x,y-1);
    }
}
int main()
{
    ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
    int n, t;
    cin >> n >> t;
    ll cnt = 1;
    for(int i = 0; i < n; i++)
    {
        ll x, y;
        cin >> x >> y;
        v.push_back({x,y});
        mp[{x,y}] = cnt;
        cnt++;
    }
    sort(v.begin(),v.end());
    check[mp[{v[0].first,v[0].second}]] = 1;
    ans.push_back(mp[{v[0].first,v[0].second}]);
    for(int i = 1; i < n; i++)
    {

        if(check[mp[{v[i].first,v[i].second}]] == 0)
        {

            if(mp[ {v[i].first-1,v[i].second}] > 0 && check[mp[ {v[i].first-1,v[i].second}]] == 1)
            {
                check[mp[ {v[i].first,v[i].second}]] = 1;
                ans.push_back(mp[{v[i].first,v[i].second}]);
            }
            else if(mp[ {v[i].first+1,v[i].second}] > 0 && check[mp[ {v[i].first+1,v[i].second}]] == 1)
            {
                check[mp[ {v[i].first,v[i].second}]] = 1;
                ans.push_back(mp[{v[i].first,v[i].second}]);
            }
            else if(mp[ {v[i].first,v[i].second-1}] > 0 && check[mp[ {v[i].first,v[i].second-1}]] == 1)
            {
                check[mp[ {v[i].first,v[i].second}]] = 1;
                ans.push_back(mp[{v[i].first,v[i].second}]);
            }
        }
        if(check[mp[{v[i].first,v[i].second}]] = 1)
        {
            doo(v[i].first,v[i].second);
        }
    }
    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;
    }
    else
    {
        cout << "NO" << endl;
    }
    return 0;
}

Compilation message (stderr)

skyscrapers.cpp: In function 'int main()':
skyscrapers.cpp:77:48: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   77 |         if(check[mp[{v[i].first,v[i].second}]] = 1)
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
skyscrapers.cpp:94:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |         for(int i = 0; i < ans.size(); i++)
      |                        ~~^~~~~~~~~~~~

• Subtask 1: 0 / 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