oj.uz

Submission #237610

# Submission time Handle Problem Language Result Execution time Memory
237610 2020-06-07T19:53:39 Z m3r8 The Forest of Fangorn (CEOI14_fangorn) C++14
15 / 100
 673 ms 65540 KB 
#include <stdio.h>
#include <set>
#include <utility>
#include <functional>
#include <vector>

#define ii std::pair<int,int>
#define N 2010
#define C 10100


int ccw(int x1 , int y1 , int x2, int 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("%d %d",&(camps[i].first), &(camps[i].second));  
  };
  int n;
  scanf("%d",&n);
  for(int i = 0;i<n;i++){
    scanf("%d %d",&(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:58:36: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
       bool ok = it == sst[j].end() && it2 == sst[j].begin() || it == sst[j].begin() && it2 == sst[j].end(); 
                 ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fangorn.cpp:69: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:29: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:31: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:33:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&c);
   ~~~~~^~~~~~~~~
fangorn.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&(camps[i].first), &(camps[i].second));  
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fangorn.cpp:39:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&n);
   ~~~~~^~~~~~~~~
fangorn.cpp:41:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&(trees[i].first), &(trees[i].second));  
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 30.0

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

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Incorrect 5 ms 640 KB Output isn't correct
4 Correct 6 ms 640 KB Output is correct
5 Correct 5 ms 640 KB Output is correct
6 Correct 7 ms 1280 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Incorrect 5 ms 640 KB Output isn't correct
10 Incorrect 11 ms 2048 KB Output isn't correct
11 Incorrect 12 ms 2176 KB Output isn't correct
12 Correct 13 ms 2304 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Incorrect 520 ms 47452 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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