oj.uz

Submission #599014

# Submission time Handle Problem Language Result Execution time Memory
599014 2022-07-19T09:04:36 Z 조영욱(#8459) The Forest of Fangorn (CEOI14_fangorn) C++17
100 / 100
 538 ms 31812 KB 
# pragma GCC optimize ("O3")
# pragma GCC optimize ("Ofast")
# pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;

int n,c;
int w,h;
typedef pair<int,int> P;
typedef pair<long long,long long> Pl;
P vec[2000][1999];
int sz[2000];
P save[10000];
P arr[2000];
int in[2000];

inline bool comp(P a,P b) {
    if ((a.second>=0)^(b.second>=0)) {
        if (a.second>=0)
            return true;
        return false;
    }
    if (a.second==0&&b.second==0) {
        return a.first>b.first;
    }
    if (1LL*a.first*b.second>1LL*b.first*a.second) {
        return true;
    }
    return false;
}

inline int f(int ind,P pos) {
    pos.first-=arr[ind].first;
    pos.second-=arr[ind].second;
    int lo=-1; //vec[ind][lo]<pos
    int hi=n-1; //vec[ind][hi]>=pos
    while (lo+1<hi) {
        int mid=(lo+hi)/2;
        if (comp(vec[ind][mid],pos)) {
            lo=mid;
        }
        else {
            hi=mid;
        }
    }
    return hi%(n-1);
}

int main() {
    scanf("%d %d",&w,&h);
    long long xg,yg;
    scanf("%lld %lld",&xg,&yg);
    scanf("%d",&c);
    for(int i=0;i<c;i++) {
        scanf("%d %d",&save[i].first,&save[i].second);
    }
    scanf("%d",&n);
    for(int i=0;i<n;i++) {
        scanf("%d %d",&arr[i].first,&arr[i].second);
    }
    for(int i=0;i<n;i++) {
        for(int j=0;j<n;j++) {
if (i==j) continue;
            vec[i][sz[i]]=P(arr[i].first-arr[j].first,arr[i].second-arr[j].second);
            sz[i]++;
        }
        sort(vec[i],vec[i]+n-1,comp);
    }
    for(int i=0;i<n;i++) {
        in[i]=f(i,P(xg,yg));
//printf("..%d\n",in[i]);
    }
    vector<int> ret;
    for(int i=0;i<c;i++) {
        bool flag=true;
        for(int j=0;j<n;j++) {
//printf("%d %d %d\n",i,j,f(j,save[i]));
            P pos=P(save[i].first-arr[j].first,save[i].second-arr[j].second);
            if (in[j]==0) {
                if (comp(vec[j][n-2],pos)||comp(pos,vec[j][0])) {

                }
                else {
                    flag=false;
                    break;
                }
            }
            else {
                if (comp(vec[j][in[j]-1],pos)&&comp(pos,vec[j][in[j]])) {

                }
                else {
                    flag=false;
                    break;
                }
            }
        }
        if (flag) {
            ret.push_back(i+1);
        }
    }
    printf("%d\n",ret.size());
    for(int i=0;i<ret.size();i++) {
        printf("%d ",ret[i]);
    }
    return 0;
}

Compilation message

fangorn.cpp: In function 'int main()':
fangorn.cpp:102:14: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
  102 |     printf("%d\n",ret.size());
      |             ~^    ~~~~~~~~~~
      |              |            |
      |              int          std::vector<int>::size_type {aka long unsigned int}
      |             %ld
fangorn.cpp:103:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |     for(int i=0;i<ret.size();i++) {
      |                 ~^~~~~~~~~~~
fangorn.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |     scanf("%d %d",&w,&h);
      |     ~~~~~^~~~~~~~~~~~~~~
fangorn.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |     scanf("%lld %lld",&xg,&yg);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
fangorn.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |     scanf("%d",&c);
      |     ~~~~~^~~~~~~~~
fangorn.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         scanf("%d %d",&save[i].first,&save[i].second);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fangorn.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
fangorn.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         scanf("%d %d",&arr[i].first,&arr[i].second);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 596 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 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 2 ms 980 KB Output is correct
7 Correct 1 ms 312 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 3 ms 1204 KB Output is correct
11 Correct 3 ms 1328 KB Output is correct
12 Correct 3 ms 1364 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 97 ms 12048 KB Output is correct
5 Correct 21 ms 4000 KB Output is correct
6 Correct 380 ms 31564 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 400 ms 31672 KB Output is correct
2 Correct 538 ms 31812 KB Output is correct
3 Correct 376 ms 31724 KB Output is correct
4 Correct 222 ms 31784 KB Output is correct