Submission #503292

#	Time	Username	Problem	Language	Result	Execution time	Memory
503292		BERNARB01	Building Skyscrapers (CEOI19_skyscrapers)	C++17	0 / 100	3570 ms	7956 KiB

skyscrapers

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, subtask;
  cin >> n >> subtask;
  vector<pair<int, int>> p(n);
  map<int, int> mp;
  for (int i = 0; i < n; i++) {
    cin >> p[i].first >> p[i].second;
    mp[p[i].first] = mp[p[i].second] = 0;
  }
  int idd = 0;
  for (auto& pp : mp) {
    pp.second = idd++;
  }
  vector<pair<int, int>> rp = p;
  for (int i = 0; i < n; i++) {
    p[i].first = mp[p[i].first];
    p[i].second = mp[p[i].second];
  }
  sort(p.begin(), p.end());
  vector<int> per(n);
  iota(per.begin(), per.end(), 0);
  do {
    bool bl = true;
    map<pair<int, int>, bool> vis;
    set<pair<int, int>> se;
    auto can_go = [&](int x, int y) {
      return vis[{x - 1, y - 1}] || vis[{x - 1, y}] || vis[{x - 1, y}] || vis[{x, y - 1}] || vis[{x, y + 1}] || vis[{x + 1, y - 1}] || vis[{x + 1, y}] || vis[{x + 1, y + 1}];
    };
    function<bool(int, int, int)> can_go_out = [&](int x, int y, int dph) {
      if (vis[{x, y}]) {
        return false;
      }
      if (x + 1 >= idd || y + 1 >= idd || x - 1 < 0 || y - 1 < 0) {
        return true;
      }
      if (dph == 2) {
        return true;
      }
      se.insert({x, y});
      if (!se.count({x - 1, y})) {
        if (can_go_out(x - 1, y, dph + 1)) {
          return true;
        }
      }
      if (!se.count({x + 1, y})) {
        if (can_go_out(x + 1, y, dph + 1)) {
          return true;
        }
      }
      if (!se.count({x, y - 1})) {
        if (can_go_out(x, y - 1, dph + 1)) {
          return true;
        }
      }
      if (!se.count({x, y + 1})) {
        if (can_go_out(x, y + 1, dph + 1)) {
          return true;
        }
      }
      return false;
    };
    vis[{rp[per[0]].first, rp[per[0]].second}] = 1;
    for (int i = 1; i < n; i++) {
      if (!can_go(rp[per[i]].first, rp[per[i]].second)) {
        bl = false;
      }
      vis[{rp[per[i]].first, rp[per[i]].second}] = 1;
    }
    if (!bl) {
      continue;
    }
    vis.clear();
    for (int i = 0; i < n; i++) {
      while (!se.empty()) {
        se.erase(se.begin());
      }
      if (!can_go_out(p[per[i]].first, p[per[i]].second, 0)) {
        /**
        cout << i << " " << p[per[i]].first << " " << p[per[i]].second << '\n';
        for (auto pp : vis) {
          cout << pp.first.first << " " << pp.first.second << '\n';
        }
        **/
        bl = false;
        break;
      }
      vis[{p[per[i]].first, p[per[i]].second}] = 1;
    }
    if (!bl) {
      continue;
    }
    cout << "YES" << '\n';
    for (int i = 0; i < n; i++) {
      if (i > 0) {
        cout << " ";
      }
      cout << per[i] + 1;
    }
    cout << '\n';
    return 0;
  } while (next_permutation(per.begin(), per.end()));
  cout << "NO" << '\n';
  return 0;
}

• 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