oj.uz

Submission #567078

# Submission time Handle Problem Language Result Execution time Memory
567078 2022-05-23T07:53:32 Z 600Mihnea The Forest of Fangorn (CEOI14_fangorn) C++17
50 / 100
 3000 ms 716 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 w,h;
int n,c;
int cnt_good[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);
}

int get_type(Vector a) {
  assert(a.x==0||a.x==w||a.y==0||a.y==h);

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

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) {
    assert(a.y!=b.y);
    return a.y<b.y;
  }
  if (type==1) {
    assert(a.x!=b.x);
    return a.x>b.x;
  }
  if (type==2) {
    assert(a.y!=b.y);
    return a.y>b.y;
  }
  if (type==3) {
    assert(a.x!=b.x);
    return a.x<b.x;
  }
  assert(0);
}

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

  ///freopen ("input.txt", "r", stdin);

  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++) {
   /// 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;
      /// trees[i] - origin = delta
      /// trees[i] = origin + delta
      events.push_back({{-delta.x,-delta.y}, -1});
    }
    for (int i=1;i<=c;i++) {
      events.push_back({camps[i]-origin, i});
    }
    events.push_back({myself-origin, 0});
    sort(events.begin(), events.end(),cmp);
    int cox=0;
    /*cout<<"0 0 O\n";
    for (auto &it : events) {
      cox++;

      cout<<it.first.x<<" "<<it.first.y<<" P";
      if (it.second==-1) {
        cout<<"x";
      }else{
        cout<<it.second;

      }
      cout<<"\n";
    }*/
    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;

    /*
    for (auto &j : events) {
      cout<<j.second<<" ";
    }
    cout<<" -------> ";

    cout<<" = "<<l<<" and "<<r<<"\n";
*/
    for (int j=l;j!=(r+1)%sz;j=(j+1)%sz) {
      assert(events[j].second>=0);
      if (events[j].second>0) {
        assert(1<=events[j].second&&events[j].second<=c);
        cnt_good[events[j].second]++;
      }
    }
    ///return 0;
  }
  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 main()':
fangorn.cpp:140:9: warning: unused variable 'cox' [-Wunused-variable]
  140 |     int cox=0;
      |         ^~~

Subtask #1
30.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 Correct 0 ms 212 KB Output is correct
4 Correct 1 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 212 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 3 ms 212 KB Output is correct
3 Correct 6 ms 212 KB Output is correct
4 Correct 6 ms 340 KB Output is correct
5 Correct 4 ms 224 KB Output is correct
6 Correct 14 ms 344 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 3 ms 212 KB Output is correct
9 Correct 3 ms 340 KB Output is correct
10 Correct 24 ms 340 KB Output is correct
11 Correct 25 ms 340 KB Output is correct
12 Correct 42 ms 340 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1107 ms 384 KB Output is correct
5 Correct 194 ms 352 KB Output is correct
6 Execution timed out 3045 ms 468 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 3057 ms 716 KB Time limit exceeded
2 Halted 0 ms 0 KB -