oj.uz

Submission #567043

# Submission time Handle Problem Language Result Execution time Memory
567043 2022-05-23T07:35:32 Z 600Mihnea The Forest of Fangorn (CEOI14_fangorn) C++17
50 / 100
 3000 ms 892 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;
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);
}

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

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

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

  cin>>c;
  for (int i=1;i<=c;i++) {
    camps[i]=readVector();
  }
  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:97:9: warning: unused variable 'cox' [-Wunused-variable]
   97 |     int cox=0;
      |         ^~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 324 KB Output is correct
7 Correct 5 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 4 ms 340 KB Output is correct
5 Correct 5 ms 340 KB Output is correct
6 Correct 11 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 3 ms 340 KB Output is correct
10 Correct 29 ms 340 KB Output is correct
11 Correct 26 ms 336 KB Output is correct
12 Correct 34 ms 324 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 883 ms 400 KB Output is correct
5 Correct 187 ms 360 KB Output is correct
6 Execution timed out 3066 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 3073 ms 892 KB Time limit exceeded
2 Halted 0 ms 0 KB -