oj.uz

Submission #567048

# Submission time Handle Problem Language Result Execution time Memory
567048 2022-05-23T07:37:24 Z 600Mihnea The Forest of Fangorn (CEOI14_fangorn) C++17
0 / 100
 3000 ms 732 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Vector {
  ll x;
  ll y;



  /**Vector() : x(0), y(0) {
  }

  Vector(ll x, ll y) : x(x), y(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 n,c;
Vector camps[C];
Vector trees[N];
Vector myself;

bool cmpByAngle(Vector a,Vector b) {
  return atan2(a.y, a.x)<atan2(b.y, b.x);
}

bool cmp(pair<Vector, int> a, pair<Vector, int> b) {
  return cmpByAngle(a.first, b.first);
}

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

  {
    int _, __;
    cin>>_>>__;
  }
  myself=readVector();

  cin>>c;
  vector<int> sol;
  for (int i=1;i<=c;i++) {
    camps[i]=readVector();
    sol.push_back(i);
  }
  cin>>n;
  for (int i=1;i<=n;i++) {
    trees[i]=readVector();
  }
  for (int tid=1;tid<=n;tid++) {
   /// tid=3;
    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});
    }
    for (auto &i : sol) {
      events.push_back({camps[i]-origin, i});
    }
    events.push_back({myself-origin, 0});
    sort(events.begin(), events.end(),cmp);
    int p0=0;
    while (events[p0].second!=0) p0++;
    assert(p0<(int)events.size());
    assert(events[p0].second==0);
    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;

    vector<int> ns;

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

Subtask #1
0.0 / 30.0

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

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 2 ms 212 KB Output isn't correct
3 Incorrect 3 ms 212 KB Output isn't correct
4 Correct 4 ms 212 KB Output is correct
5 Correct 4 ms 212 KB Output is correct
6 Correct 11 ms 340 KB Output is correct
7 Incorrect 0 ms 212 KB Output isn't correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 3 ms 212 KB Output is correct
10 Incorrect 22 ms 340 KB Output isn't correct
11 Incorrect 18 ms 340 KB Output isn't correct
12 Correct 27 ms 340 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 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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