oj.uz

Submission #667821

# Submission time Handle Problem Language Result Execution time Memory
667821 2022-12-02T06:07:48 Z RambaXGorilla The Forest of Fangorn (CEOI14_fangorn) C++17
100 / 100
 2272 ms 32092 KB 
#include<cstdio>
#include<algorithm>
#include<utility>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair <int,int> ii;
int N, C, W, H;
ii gimli;
ii camps[10010];
ii trees[2010];
ii rays[2010][2010];
vector <int> reach;
ii sub(ii a, ii b) {return ii(a.first - b.first, a.second - b.second);}
bool comp(ii a, ii b){
    int c = a.first + (!a.first) * a.second;
    int d = b.first + (!b.first) * b.second;
    if(!c) return false;
    if(!d) return true;
    if(c < 0 && d > 0) return false;
    if(d < 0 && c > 0) return true;
    return (ll) a.second * b.first > (ll) b.second * a.first;
}
int search(int j, ii a){
    return (upper_bound(rays[j], rays[j] + N - 1, a, comp) - rays[j]) % (N - 1);
}
int main(){
    scanf("%d%d%d%d",&W,&H,&gimli.first,&gimli.second);
    scanf("%d",&C);
    for(int i = 0;i < C;i++){
        scanf("%d%d",&camps[i].first,&camps[i].second);
    }
    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 < N;j++){
            rays[i][j] = sub(trees[i], trees[j]);
        }
        sort(rays[i], rays[i] + N, comp);
    }
    for(int i = 0;i < C;i++){
        bool poss = true;
        for(int j = 0;j < N;j++){
            if(search(j, sub(gimli, trees[j])) != search(j, sub(camps[i], trees[j]))){
                poss = false;
                break;
            }
        }
        if(poss) reach.push_back(i + 1);
    }
    printf("%d\n",reach.size());
    for(auto i : reach){
        printf("%d ",i);
    }
}

Compilation message

fangorn.cpp: In function 'int main()':
fangorn.cpp:53:14: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   53 |     printf("%d\n",reach.size());
      |             ~^    ~~~~~~~~~~~~
      |              |              |
      |              int            std::vector<int>::size_type {aka long unsigned int}
      |             %ld
fangorn.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |     scanf("%d%d%d%d",&W,&H,&gimli.first,&gimli.second);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fangorn.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |     scanf("%d",&C);
      |     ~~~~~^~~~~~~~~
fangorn.cpp:31:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         scanf("%d%d",&camps[i].first,&camps[i].second);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fangorn.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     scanf("%d",&N);
      |     ~~~~~^~~~~~~~~
fangorn.cpp:35:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |         scanf("%d%d",&trees[i].first,&trees[i].second);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 552 KB Output is correct
8 Correct 1 ms 596 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 4 ms 1236 KB Output is correct
11 Correct 4 ms 1364 KB Output is correct
12 Correct 4 ms 1320 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 352 KB Output is correct
4 Correct 95 ms 12088 KB Output is correct
5 Correct 24 ms 3872 KB Output is correct
6 Correct 392 ms 31788 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 682 ms 31896 KB Output is correct
2 Correct 2272 ms 32092 KB Output is correct
3 Correct 422 ms 31896 KB Output is correct
4 Correct 1617 ms 31984 KB Output is correct