oj.uz

Submission #793211

# Submission time Handle Problem Language Result Execution time Memory
793211 2023-07-25T16:01:33 Z peijar The Forest of Fangorn (CEOI14_fangorn) C++17
50 / 100
 3000 ms 884 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());
    for (auto [x, y, p] : rays)
      dbg(x, y, p);

    vector<int> nxtSol;
    pt r = init - arbres[i];
    Angle rayInit(r.x, r.y);
    dbg(rayInit.x, rayInit.y);
    auto findPos = [&](Angle a) {
      int u = 0;
      while (not(rays[u] < a and a < rays[u + 1]))
        u++;
      return u;
    };
    for (int c : sol) {
      pt p = camps[c] - arbres[i];
      Angle ray(p.x, p.y);
      dbg(ray.x, ray.y);
      int u = findPos(rayInit) % (nbArbres - 1);
      int v = findPos(ray) % (nbArbres - 1);
      // int u = lower_bound(rays.begin(), rays.end(), rayInit) - rays.begin();
      // int v = lower_bound(rays.begin(), rays.end(), ray) - rays.begin();
      // int u
      dbg(u, v);
      if (u == v)
        nxtSol.push_back(c);
    }
    sol = nxtSol;
  }

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

Compilation message

fangorn.cpp: In function 'int main()':
fangorn.cpp:130:15: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
  130 |     for (auto [x, y, p] : rays)
      |               ^~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 324 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 324 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 2 ms 320 KB Output is correct
8 Correct 2 ms 320 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 3 ms 212 KB Output is correct
4 Correct 2 ms 320 KB Output is correct
5 Correct 2 ms 320 KB Output is correct
6 Correct 8 ms 356 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 14 ms 372 KB Output is correct
11 Correct 17 ms 340 KB Output is correct
12 Correct 18 ms 324 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 448 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3056 ms 884 KB Time limit exceeded
2 Halted 0 ms 0 KB -