oj.uz

Submission #237613

# Submission time Handle Problem Language Result Execution time Memory
237613 2020-06-07T20:01:28 Z m3r8 The Forest of Fangorn (CEOI14_fangorn) C++14
50 / 100
 571 ms 65540 KB 
#include <stdio.h>
#include <set>
#include <utility>
#include <functional>
#include <vector>

#define ii std::pair<long long ,long long>
#define N 3000
#define C 20100
#define ll long long


ll ccw(ll x1 , ll y1 , ll x2, ll y2){
  return x1 * y2 - x2 * y1;  
};

ii camps[C];
ii trees[N];

struct cmp{
  bool operator()(ii a, ii b){
    return ccw(a.first, a.second, b.first, b.second) >= 0; 
  };  
};

std::set<ii, cmp> sst[N];

int main(void){
  int w,h;
  scanf("%d %d",&w, &h);
  int xg, yg;
  scanf("%d %d",&xg, &yg);
  int c;
  scanf("%d",&c);

  for(int i = 0;i<c;i++){
    scanf("%lld %lld",&(camps[i].first), &(camps[i].second));  
  };
  int n;
  scanf("%d",&n);
  for(int i = 0;i<n;i++){
    scanf("%lld %lld",&(trees[i].first), &(trees[i].second));  
  };

  for(int i = 0;i<n;i++){
    for(int j = 0;j<i;j++){
      sst[i].insert({trees[i].first - trees[j].first, trees[i].second-trees[j].second});
      sst[j].insert({trees[j].first - trees[i].first, trees[j].second-trees[i].second});
    };  
  };

  std::vector<int> erg;

  bool pos = 1;
  for(int i = 0;i<c;i++){
    for(int j = 0;j<n;j++){
      auto it = sst[j].upper_bound({camps[i].first - trees[j].first, camps[i].second - trees[j].second});  
      auto it2 = sst[j].upper_bound({xg - trees[j].first, yg - trees[j].second});
      bool ok = (it == sst[j].end() && it2 == sst[j].begin()) || (it == sst[j].begin() && it2 == sst[j].end()); 
      if(it != it2 && !ok){
        pos = 0;  
      };
    };
    if(pos){
      erg.push_back(i+1);  
    };
    pos = 1;
  };
  
  printf("%d\n",erg.size());
  for(auto i: erg){
    printf("%d ",i);  
  };
  if(erg.size())puts("");

  return 0;  
};

Compilation message

fangorn.cpp: In function 'int main()':
fangorn.cpp:70:27: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
   printf("%d\n",erg.size());
                 ~~~~~~~~~~^
fangorn.cpp:30:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&w, &h);
   ~~~~~^~~~~~~~~~~~~~~~
fangorn.cpp:32:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&xg, &yg);
   ~~~~~^~~~~~~~~~~~~~~~~~
fangorn.cpp:34:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&c);
   ~~~~~^~~~~~~~~
fangorn.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld",&(camps[i].first), &(camps[i].second));  
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fangorn.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&n);
   ~~~~~^~~~~~~~~
fangorn.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld",&(trees[i].first), &(trees[i].second));  
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 512 KB Output is correct
4 Correct 4 ms 512 KB Output is correct
5 Correct 4 ms 512 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 768 KB Output is correct
8 Correct 6 ms 768 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 5 ms 896 KB Output is correct
5 Correct 6 ms 896 KB Output is correct
6 Correct 8 ms 1536 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Correct 5 ms 768 KB Output is correct
10 Correct 10 ms 2560 KB Output is correct
11 Correct 12 ms 2816 KB Output is correct
12 Correct 12 ms 2944 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 512 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 571 ms 63004 KB Output is correct
5 Correct 72 ms 14584 KB Output is correct
6 Runtime error 421 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 427 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -