Submission #1307034

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307034		LucaLucaM	Building Skyscrapers (CEOI19_skyscrapers)	C++20	34 / 100	3594 ms	49628 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 (ll) P.x * P.x + (ll) P.y * 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;
    }
    
    vis.assign(n, false);
    
    std::vector<int> st;

    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]) {
            st.push_back(j);
          }
        }
      }
    };

    st.push_back(0);

    std::vector<int> order;

    while (!st.empty()) {
      int who = 0;
      for (int i = 1; i < (int) st.size(); i++) {
        if (norm(a[st[i]] - a[0]) < norm(a[st[who]] - a[0])) {
          who = i;
        }
      }
      int i = st[who];
      st.erase(st.begin() + who);
      if (vis[i]) {
        continue;
      }
      order.push_back(i);
      vis[i] = true;
      add_neighbours(i);
    }

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

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

  return 0;
}

• 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