Submission #1307037

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307037		LucaLucaM	Building Skyscrapers (CEOI19_skyscrapers)	C++20	8 / 100	1 ms	576 KiB

skyscrapers

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

#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++) {
      auto &[x, y] = a[i];
      std::cin >> x >> y;
      mp[{x, 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;
    }
    
    std::vector<int> order(n);
    for (int i = 0; i < n; i++) {
      order[i] = i;
    }

    std::sort(order.begin(), order.end(), [&](int i, int j) {
      Point A = a[i] - a[0];
      Point B = a[j] - a[0];
      if (norm(A) != norm(B)) {
        return norm(A) < norm(B);
      } else {
        return A.x < B.x;
      }
    });


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

  return 0;
}

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