oj.uz

Submission #237612

# Submission time Handle Problem Language Result Execution time Memory
237612 2020-06-07T19:59:54 Z m3r8 The Forest of Fangorn (CEOI14_fangorn) C++14
50 / 100
 551 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("%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:37:56: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
     scanf("%d %d",&(camps[i].first), &(camps[i].second));  
                   ~~~~~~~~~~~~~~~~~                    ^
fangorn.cpp:37:56: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
fangorn.cpp:42:56: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
     scanf("%d %d",&(trees[i].first), &(trees[i].second));  
                   ~~~~~~~~~~~~~~~~~                    ^
fangorn.cpp:42:56: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
fangorn.cpp:59: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: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("%d %d",&(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("%d %d",&(trees[i].first), &(trees[i].second));  
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 512 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 512 KB Output is correct
7 Correct 5 ms 768 KB Output is correct
8 Correct 5 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 6 ms 768 KB Output is correct
5 Correct 5 ms 768 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 11 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 560 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 551 ms 62968 KB Output is correct
5 Correct 73 ms 14584 KB Output is correct
6 Runtime error 422 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 438 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -