oj.uz

Submission #793218

# Submission time Handle Problem Language Result Execution time Memory
793218 2023-07-25T16:03:59 Z peijar The Forest of Fangorn (CEOI14_fangorn) C++17
100 / 100
 2745 ms 1252 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
  bool first = true;
  string res = "[";
  for (const auto &x : v) {
    if (!first)
      res += ", ";
    first = false;
    res += to_string(x);
  }
  res += "]";
  return res;
}

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
  cout << ' ' << to_string(H);
  dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

template <typename T> struct Point {
  T x, y;

  Point() : x(0), y(0) {}

  Point(T _x, T _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);
  }

  Point operator*(const T lambda) const {
    return Point(x * lambda, y * lambda);
  }

  Point operator/(const T lambda) const {
    return Point(x / lambda, y / lambda);
  }

  bool operator<(const Point &other) const {
    return tie(x, y) < tie(other.x, other.y);
  }
  bool operator==(const Point &other) const {
    return tie(x, y) == tie(other.x, other.y);
  }
  bool operator>(const Point &other) const { return other < *this; }
  bool operator!=(const Point &other) const { return !(*this == other); }
  bool operator<=(const Point &other) const { return !(other < *this); }
  bool operator>=(const Point &other) const { return other <= *this; }

  friend ostream &operator<<(ostream &out, const Point &a) {
    return out << a.x << " " << a.y;
  }
  friend istream &operator>>(istream &in, Point &a) { return in >> a.x >> a.y; }
  friend T dot(const Point a, const Point b) { return a.x * b.x + a.y * b.y; }

  friend T cross(const Point a, const Point b) { return a.x * b.y - a.y * b.x; }

  friend T dis2(const Point a, const Point b) { return dot(b - a, b - a); }
};

using pt = Point<int>;

struct Angle {
  int x, y;
  int t;
  Angle(int x, int y, int t = 0) : x(x), y(y), t(t) {}
  Angle operator-(Angle b) const { return {x - b.x, y - b.y, t}; }
  int half() const {
    assert(x || y);
    return y < 0 || (y == 0 && x < 0);
  }
  Angle t90() const { return {-y, x, t + (half() && x >= 0)}; }
  Angle t180() const { return {-x, -y, t + half()}; }
  Angle t360() const { return {x, y, t + 1}; }
};
bool operator<(Angle a, Angle b) {
  // add a . dist2 () and b . dist2 () to also compare distances
  return make_tuple(a.t, a.half(), a.y * (int)b.x) <
         make_tuple(b.t, b.half(), a.x * (int)b.y);
}

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int w, h;
  cin >> w >> h;
  pt init;
  cin >> init;

  int nbCamps;
  cin >> nbCamps;
  vector<pt> camps(nbCamps);
  for (pt &p : camps)
    cin >> p;
  int nbArbres;
  cin >> nbArbres;
  vector<pt> arbres(nbArbres);

  for (pt &p : arbres)
    cin >> p;

  vector<int> sol(nbCamps);
  iota(sol.begin(), sol.end(), 0);
  for (int i = 0; i < nbArbres; ++i) {
    vector<Angle> rays;
    for (int j = 0; j < nbArbres; ++j)
      if (i != j) {
        pt p = arbres[i] - arbres[j];
        rays.emplace_back(p.x, p.y);
        rays.emplace_back(p.x, p.y, 1);
        rays.emplace_back(p.x, p.y, -1);
      }
    sort(rays.begin(), rays.end());

    vector<int> nxtSol;
    pt r = init - arbres[i];
    Angle rayInit(r.x, r.y);
    int u = lower_bound(rays.begin(), rays.end(), rayInit) - rays.begin();
    for (int c : sol) {
      pt p = camps[c] - arbres[i];
      Angle ray(p.x, p.y);
      int v = lower_bound(rays.begin(), rays.end(), ray) - rays.begin();
      while (u >= nbArbres - 1)
        u -= nbArbres - 1;
      while (v >= nbArbres - 1)
        v -= nbArbres - 1;
      if (u == v)
        nxtSol.push_back(c);
    }
    sol = nxtSol;
  }

  cout << sol.size() << endl;
  for (int x : sol)
    cout << x + 1 << ' ';
  cout << endl;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 2 ms 212 KB Output is correct
8 Correct 2 ms 212 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 212 KB Output is correct
4 Correct 2 ms 212 KB Output is correct
5 Correct 2 ms 236 KB Output is correct
6 Correct 6 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 2 ms 212 KB Output is correct
10 Correct 11 ms 356 KB Output is correct
11 Correct 12 ms 340 KB Output is correct
12 Correct 13 ms 340 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 391 ms 508 KB Output is correct
5 Correct 79 ms 340 KB Output is correct
6 Correct 1671 ms 912 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1825 ms 952 KB Output is correct
2 Correct 2745 ms 1076 KB Output is correct
3 Correct 1710 ms 1168 KB Output is correct
4 Correct 2008 ms 1252 KB Output is correct