oj.uz

Submission #567125

# Submission time Handle Problem Language Result Execution time Memory
567125 2022-05-23T08:17:27 Z 600Mihnea The Forest of Fangorn (CEOI14_fangorn) C++17
50 / 100
 3000 ms 888 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double ld;

struct Vector {
  ll x;
  ll y;
};

Vector operator + (Vector a, Vector b) {
  return { a.x + b.x, a.y + b.y };
}

Vector operator - (Vector a, Vector b) {
  return { a.x - b.x, a.y - b.y };
}

Vector operator * (Vector a, ll b) {
  return { a.x * b, a.y * b };
}


Vector operator * (ll b, Vector a) {
  return { a.x * b, a.y * b };
}


Vector readVector() {
  int x, y;
  cin >> x >> y;
  return { x, y };
}

const int N = 2000 + 7;
const int C = 10000 + 7;

int w, h;
int n, c;
int cnt_good[C];
Vector camps[C];
Vector trees[N];
Vector myself;


bool cmp(pair<Vector, int> a, pair<Vector, int> b) {
  return atan2((ld)a.first.y, (ld)a.first.x) < atan2((ld)b.first.y, (ld)b.first.x);
}

int get_type(Vector a) {

  if (a.x == w) return 0;
  if (a.y == h) return 1;
  if (a.x == 0) return 2;
  if (a.y == 0) return 3;
}

bool cmpOnRect(int i, int j) {
  Vector a = camps[i];
  Vector b = camps[j];

  int type_a = get_type(a);
  int type_b = get_type(b);
  if (type_a != type_b) return type_a < type_b;
  int type = type_a;

  if (type == 0) {
    return a.y < b.y;
  }
  if (type == 1) {
    return a.x > b.x;
  }
  if (type == 2) {
    return a.y > b.y;
  }
  if (type == 3) {
    return a.x < b.x;
  }
}

signed main() {
  ios::sync_with_stdio(0); cin.tie(0);

  cin >> w >> h;
  myself = readVector();

  vector<int> inds;

  cin >> c;
  for (int i = 1; i <= c; i++) {
    camps[i] = readVector();
    inds.push_back(i);
  }
  sort(inds.begin(), inds.end(), cmpOnRect);

  cin >> n;
  for (int i = 1; i <= n; i++) {
    trees[i] = readVector();
  }
  for (int tid = 1; tid <= n; tid++) {
    Vector origin = trees[tid];
    vector<pair<Vector, int>> events;
    for (int i = 1; i <= n; i++) {
      if (i == tid) continue;
      Vector delta = trees[i] - origin;
      events.push_back({ {-delta.x,-delta.y}, -1 });
    }
    events.push_back({ myself - origin, 0 });
    auto cop_events = events;

    ld minAng = (ld)1e18;
    int start = -1;

    for (int P = 0; P < c; P++) {
      int i = inds[P];
      Vector vec = camps[i] - origin;
      ld ang = atan2(vec.y, vec.x);
      if (ang < minAng) {
        minAng = ang;
        start = P;
      }
    }

    vector<pair<Vector, int>> cps;
    for (int l = 0; l < c; l++) {
      int i = inds[(start + l) % c];
      cps.push_back({ camps[i] - origin, i });
    }

    sort(cop_events.begin(), cop_events.end(), cmp);
   /// sort(cps.begin(), cps.end(), cmp);
    vector<pair<Vector, int>> so;

    int p1 = 0, p2 = 0;
    while (p1 < (int)cps.size() && p2 < (int)cop_events.size()) {
      if (cmp(cps[p1], cop_events[p2])) {
        so.push_back(cps[p1++]);
      }
      else {
        so.push_back(cop_events[p2++]);
      }
    }
    while (p1 < (int)cps.size()) {
      so.push_back(cps[p1++]);
    }

    while (p2 < (int)cop_events.size()) {
      so.push_back(cop_events[p2++]);
    }

    events = so;
    int p0 = 0;
    while (events[p0].second != 0) p0++;

    int l = p0, r = p0, sz = (int)events.size();

    while (events[(l + sz - 1) % sz].second != -1) l = (l + sz - 1) % sz;
    while (events[(r + 1) % sz].second != -1) r = (r + 1) % sz;

    for (int j = l; j != (r + 1) % sz; j = (j + 1) % sz) {
      if (events[j].second > 0) {
        cnt_good[events[j].second]++;
      }
    }
  }
  vector<int> sol;
  for (int i = 1; i <= c; i++) {
    if (cnt_good[i] == n) {
      sol.push_back(i);
    }
  }
  cout << (int)sol.size() << "\n";
  for (auto& i : sol) {
    cout << i << " ";
  }
  cout << "\n";
}

Compilation message

fangorn.cpp: In function 'int get_type(Vector)':
fangorn.cpp:58:1: warning: control reaches end of non-void function [-Wreturn-type]
   58 | }
      | ^
fangorn.cpp: In function 'bool cmpOnRect(int, int)':
fangorn.cpp:81:1: warning: control reaches end of non-void function [-Wreturn-type]
   81 | }
      | ^

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 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 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 4 ms 340 KB Output is correct
8 Correct 3 ms 340 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 2 ms 340 KB Output is correct
3 Correct 5 ms 340 KB Output is correct
4 Correct 5 ms 340 KB Output is correct
5 Correct 5 ms 340 KB Output is correct
6 Correct 12 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 4 ms 340 KB Output is correct
10 Correct 26 ms 340 KB Output is correct
11 Correct 20 ms 364 KB Output is correct
12 Correct 30 ms 360 KB Output is correct

Subtask #3
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 846 ms 440 KB Output is correct
5 Correct 163 ms 380 KB Output is correct
6 Execution timed out 3064 ms 748 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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