Submission #1245573

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245573		abdelhakim	Building Skyscrapers (CEOI19_skyscrapers)	C++20	54 / 100	582 ms	76240 KiB

skyscrapers

#include <bits/stdc++.h>
#define ll long long
#define inf (ll)(1e15) 
#define mod (ll)1e9+7
#define dbg(x) cerr <<#x << ' ' << x <<endl;
using namespace std;

void printvec(vector<ll>& v)
{
  for (auto &&i : v)
  {
    cout <<i<<' ';
  }
  cout << endl;
}
map<pair<ll,ll>,bool> vis;
map<pair<ll,ll>,ll> ra9m;
vector<pair<ll,ll>> good(pair<ll,ll> cell)
{
  vector<pair<ll,ll>> cells;
  vector<ll> pr={0,-1,1};
  for (int i=0;i<3;i++)
  {
    for (int j=0;j<3;j++)
    {
      if(i==0 && j==0)continue;
      ll v1=pr[i];
      ll v2=pr[j];
      if(!vis[{cell.first+v1,cell.second+v2}] && ra9m[{cell.first+v1,cell.second+v2}])
      {
        cells.push_back({cell.first+v1,cell.second+v2});
      }
    }
  }
  return cells;
}
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  ll n;
  cin>>n;
  ll t;
  cin>>t;
  priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> pq;
  pair<ll,ll> minp={inf,inf};
  for (int i=0;i<n;i++)
  {
    ll c, r;
    cin>>c>>r;
    ra9m[{c,r}]=i+1;
    minp=min(minp,{c,r});
  }
  vector<ll> s;
  pq.push(minp);
  while(!pq.empty())
  {
    pair<ll,ll> tp=pq.top();
    pq.pop();
    if(vis[tp])
    {
      continue;
    }
    vis[tp]=1;
    s.push_back(ra9m[tp]);
    vector<pair<ll,ll>> vec=good(tp);
    for (auto &&e : vec)
    {
      pq.push(e);
    }
  }
  if(s.size()!=n)
  {
    cout << "NO" << endl;
  }
  else
  {
    cout <<"YES"<<endl;
    for (int i=0;i<n;i++)
    {
      cout << s[i]<<endl;
    }
  }
}

• 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