oj.uz

Submission #237614

# Submission time Handle Problem Language Result Execution time Memory
237614 2020-06-07T20:14:55 Z m3r8 The Forest of Fangorn (CEOI14_fangorn) C++14
100 / 100
 1074 ms 888 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];
int pss[C];

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

std::set<ii, cmp> sst;

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++){
    sst.clear();
    for(int j = 0;j<n;j++){
      if(i != j){
        sst.insert({trees[i].first - trees[j].first, trees[i].second-trees[j].second});
      };
    };  
    for(int j = 0;j<c;j++){
      if(!pss[j]){
        auto it = sst.upper_bound({camps[j].first - trees[i].first, camps[j].second - trees[i].second});  
        auto it2 = sst.upper_bound({xg - trees[i].first, yg - trees[i].second});
        bool ok = (it == sst.end() && it2 == sst.begin()) || (it == sst.begin() && it2 == sst.end()); 
        if(it != it2 && !ok){
          pss[j] = 1;
        };    
      };
    };
  };

  std::vector<int> erg;

  for(int i = 0;i<c;i++){
    if(!pss[i])erg.push_back(i+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:31: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:33: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:35:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&c);
   ~~~~~^~~~~~~~~
fangorn.cpp:38: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:41:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&n);
   ~~~~~^~~~~~~~~
fangorn.cpp:43: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 4 ms 256 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 4 ms 256 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 4 ms 256 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 5 ms 384 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 4 ms 256 KB Output is correct
9 Correct 5 ms 256 KB Output is correct
10 Correct 8 ms 384 KB Output is correct
11 Correct 9 ms 384 KB Output is correct
12 Correct 9 ms 384 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 4 ms 256 KB Output is correct
4 Correct 153 ms 444 KB Output is correct
5 Correct 32 ms 384 KB Output is correct
6 Correct 611 ms 384 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 692 ms 512 KB Output is correct
2 Correct 1074 ms 888 KB Output is correct
3 Correct 637 ms 888 KB Output is correct
4 Correct 813 ms 888 KB Output is correct