Submission #1307043

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307043		LucaLucaM	Building Skyscrapers (CEOI19_skyscrapers)	C++20	0 / 100	1 ms	568 KiB

skyscrapers

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <map>
#include <set>

#define debug(x) #x << " = " << x << '\n'
using ll = long long;

const int dx[8] = {-1, 0, +1, 0, -1, -1, +1, +1};
const int dy[8] = {0, -1, 0, +1, -1, +1, -1, +1};

struct Point {
  int x, y;
  Point() {} 
  Point(int _x, int _y) : x(_x), y(_y) {}
  
  Point operator + (const Point &other) const {return Point(x + other.x, y + other.y);}
  Point operator - (const Point &other) const {return Point(x - other.x, y - other.y);}
  void operator += (const Point &other) {*this = *this + other;}
  void operator -= (const Point &other) {*this = *this - other;}

  friend ll norm(Point P) {
    return std::max(std::abs(P.x), std::abs(P.y));
  }
};

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);
  std::cout.tie(0);

  int n, cer;
  std::cin >> n >> cer;
  
  if (cer == 1) {
    std::vector<Point> a(n);
    std::map<std::pair<int, int>, int> mp;

    for (int i = 0; i < n; i++) {
      std::cin >> a[i].x >> a[i].y;
    }

    Point shift = a[0];
    for (int i = 0; i < n; i++) {
      a[i] -= shift;
      mp[{a[i].x, a[i].y}] = i;
    }



    std::vector<bool> vis(n, false);

    auto dfs = [&](auto &&self, int i) -> void {
      vis[i] = true;
      auto [x, y] = a[i];
      for (int k = 0; k < 8; k++) {
        int xx = x + dx[k];
        int yy = y + dy[k];
        if (mp.count({xx, yy})) {
          int j = mp[{xx, yy}];
          if (!vis[j]) {
            self(self, j);
          }
        }
      }
    };

    dfs(dfs, 0);
    
    if (std::count(vis.begin(), vis.end(), true) != n) {
      std::cout << "NO";
      return 0;
    }
    
    vis.assign(n, false);
    
    for (int i = 0; i < n; i++) {
      a[i] -= a[0];
      assert(norm(a[i]) <= n);
    }
    
    std::set<std::pair<ll, int>> st;

    auto add = [&](int i) -> void {
      st.insert({norm(a[i]), i});
    };

    auto add_neighbours = [&](int i) {
      auto [x, y] = a[i];
      for (int k = 0; k < 8; k++) {
        int xx = x + dx[k], yy = y + dy[k];
        if (mp.count({xx, yy})) {
          int j = mp[{xx, yy}];
          if (!vis[j]) {
            add(j);
          }
        }
      }
    };

    add(0);
    
    std::vector<int> order;

    while (!st.empty()) {
      int i = (*st.begin()).second;
      st.erase(st.begin());
      if (vis[i]) {
        continue;
      }
      order.push_back(i);
      vis[i] = true;
      add_neighbours(i);
    }

    assert((int) order.size() == n);

    for (int i = 0; i + 1 < n; i++) {
      assert(norm(a[i]) <= norm(a[i + 1]));
    }

    std::cout << "YES\n";
    for (int i : order) {
      std::cout << i + 1 << ' ';
    }
  }

  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