Submission #1245527

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245527		abdelhakim	Building Skyscrapers (CEOI19_skyscrapers)	C++20	34 / 100	3594 ms	36564 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;
bool good(pair<ll,ll> cell)
{
  vector<ll> pr={0,-1,1};
  for (int i=0;i<3;i++)
  {
    for (int j=0;j<3;j++)
    {
      ll v1=pr[i];
      ll v2=pr[j];
      if(vis[{cell.first+v1,cell.second+v2}])
      {
        return true;
      }
    }
  }
  return false;
}
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  ll n;
  cin>>n;
  ll t;
  cin>>t;
  set<pair<ll,ll>> st;
  for (int i=0;i<n;i++)
  {
    ll c, r;
    cin>>c>>r;
    st.insert({c,r});
    ra9m[{c,r}]=i+1;
  }
  vis[*st.begin()]=1;
  vector<ll> s;
  s.push_back(ra9m[*st.begin()]);
  st.erase(st.begin());
  bool possible=true;
  while(!st.empty())
  {
    bool did=false;
    for (auto &&e : st)
    {
      if(good(e))
      {
        did=true;
        vis[e]=1;
        st.erase(e);
        s.push_back(ra9m[e]);
        break;
      }
    }
    if(!did)
    {
      possible=false;
      break;
    }
  }
  if(!possible)
  {
    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: 0 / 20
• Subtask 6: 0 / 10
• Subtask 7: 0 / 19