oj.uz

Submission #599002

# Submission time Handle Problem Language Result Execution time Memory
599002 2022-07-19T08:52:10 Z 조영욱(#8459) The Forest of Fangorn (CEOI14_fangorn) C++17
80 / 100
 3000 ms 31696 KB 
#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];

long long ccw(P x,P y,P z) {
    Pl a=x;
    Pl b=y;
    Pl c=z;
    return a.first*b.second+b.first*c.second+c.first*a.second-a.second*b.first-b.second*c.first-c.second*a.first;
}

bool comp(P a,P b) {
    if (a.second>=0&&b.second<0) {
        return true;
    }
    if (a.second<0&&b.second>=0) {
        return false;
    }
    if (a.second==0&&b.second==0) {
        return a.first>b.first;
    }
    if (ccw(P(0,0),a,b)>0) {
        return true;
    }
    return false;
}

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]));
            if (f(j,save[i])!=in[j]) {
                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:92:14: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   92 |     printf("%d\n",ret.size());
      |             ~^    ~~~~~~~~~~
      |              |            |
      |              int          std::vector<int>::size_type {aka long unsigned int}
      |             %ld
fangorn.cpp:93:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for(int i=0;i<ret.size();i++) {
      |                 ~^~~~~~~~~~~
fangorn.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |     scanf("%d %d",&w,&h);
      |     ~~~~~^~~~~~~~~~~~~~~
fangorn.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |     scanf("%lld %lld",&xg,&yg);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
fangorn.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |     scanf("%d",&c);
      |     ~~~~~^~~~~~~~~
fangorn.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         scanf("%d %d",&save[i].first,&save[i].second);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fangorn.cpp:62:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
fangorn.cpp:64:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |         scanf("%d %d",&arr[i].first,&arr[i].second);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
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 0 ms 212 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 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 1 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 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 3 ms 1236 KB Output is correct
11 Correct 3 ms 1412 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 0 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 89 ms 12036 KB Output is correct
5 Correct 24 ms 3924 KB Output is correct
6 Correct 377 ms 31556 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 790 ms 31632 KB Output is correct
2 Execution timed out 3016 ms 31696 KB Time limit exceeded
3 Halted 0 ms 0 KB -