oj.uz

Submission #599006

# Submission time Handle Problem Language Result Execution time Memory
599006 2022-07-19T08:56:32 Z 조영욱(#8459) The Forest of Fangorn (CEOI14_fangorn) C++17
80 / 100
 3000 ms 31660 KB 
#pragma GCC optimize "O3"
#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]));
            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:85:14: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   85 |     printf("%d\n",ret.size());
      |             ~^    ~~~~~~~~~~
      |              |            |
      |              int          std::vector<int>::size_type {aka long unsigned int}
      |             %ld
fangorn.cpp:86:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for(int i=0;i<ret.size();i++) {
      |                 ~^~~~~~~~~~~
fangorn.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |     scanf("%d %d",&w,&h);
      |     ~~~~~^~~~~~~~~~~~~~~
fangorn.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |     scanf("%lld %lld",&xg,&yg);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
fangorn.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |     scanf("%d",&c);
      |     ~~~~~^~~~~~~~~
fangorn.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         scanf("%d %d",&save[i].first,&save[i].second);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fangorn.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
fangorn.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |         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 1 ms 212 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 212 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 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 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 3 ms 1236 KB Output is correct
11 Correct 3 ms 1364 KB Output is correct
12 Correct 4 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 84 ms 12140 KB Output is correct
5 Correct 18 ms 3928 KB Output is correct
6 Correct 306 ms 31476 KB Output is correct

Subtask #4
0 / 20.0

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