oj.uz

답안 #586963

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
586963 2022-07-01T06:40:14 Z 반딧불(#8396) Mixture (BOI20_mixture) C++17
13 / 100
 2000 ms 436 KB 
#include <bits/stdc++.h>

using namespace std;

#if 1
typedef long long ll;
#else
typedef __int128 ll;
#endif

struct Frac{
    ll a, b;
    Frac(){}
    Frac(ll a, ll b): a(a), b(b){
        ll g = __gcd(a, b);
        a/=g, b/=g;
        if(b<0) a=-a, b=-b;
        assert(b>0);
    }
    Frac(ll a): a(a){
        b=1;
    }

    Frac operator+(const Frac &r)const{
        ll g = __gcd(b, r.b);
        return Frac(a*(r.b/g)+r.a*(b/g), b/g*r.b);
    }

    Frac operator-(const Frac &r)const{
        ll g = __gcd(b, r.b);
        return Frac(a*(r.b/g)-r.a*(b/g), b/g*r.b);
    }

    Frac operator*(const Frac &r)const{
        return Frac(a*r.a, b*r.b);
    }

    bool operator<(const Frac &r)const{
        return a*r.b < b*r.a;
    }

    bool operator<=(const Frac &r)const{
        return a*r.b <= b*r.a;
    }

    bool operator>(const Frac &r)const{
        return a*r.b > b*r.a;
    }

    bool operator==(const Frac &r)const{
        return a*r.b == b*r.a;
    }
};

struct vector2{
    Frac x, y;
    vector2(){}
    vector2(Frac x, Frac y): x(x), y(y){}

    vector2 operator-(const vector2 r)const{
        return vector2(x-r.x, y-r.y);
    }

    bool operator<(const vector2 &r)const{
        return make_pair(x, y) < make_pair(r.x, r.y);
    }

    bool operator==(const vector2 &r)const{
        return x==r.x && y==r.y;
    }

    Frac cross(vector2 r)const{
        return x*r.y - y*r.x;
    }
};

Frac ccw(vector2 a, vector2 b){
    return a.cross(b);
}

Frac ccw(vector2 a, vector2 b, vector2 c){
    return (b-a).cross(c-a);
}

vector2 point;
int n;
vector2 arr[100002];
bool deleted[100002];
int arrSize;

void input(vector2 &p){
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    p.x = Frac(a, a+b+c);
    p.y = Frac(b, a+b+c);
}

vector<vector2> hull(vector<vector2> &vec){
    vector<vector2> ret;
    sort(vec.begin(), vec.end());
    sort(vec.begin()+1, vec.end(), [&](vector2 A, vector2 B){
        Frac tmp = ccw(A, vec[0], B);
        if(tmp == 0) return A.x+A.y < B.x+B.y;
        return tmp < 0;
    });
    ret.push_back(vec[0]);
    for(int i=1; i<(int)vec.size(); i++){
        while(ret.size()>=2 && ccw(ret[ret.size()-2], ret.back(), vec[i]) <= 0) ret.pop_back();
        ret.push_back(vec[i]);
    }
    return ret;
}

inline int sign(Frac x){
    if(x>0) return 1;
    if(x<0) return -1;
    return 0;
}

bool inside(vector<vector2> &vec, vector2 p){
    for(auto x: vec) if(x==p) return false;
    return true;
}

void calc(){
    vector<vector2> vec;
    for(int i=1; i<=arrSize; i++){
        if(!deleted[i]){
            if(arr[i] == point){
                puts("1");
                return;
            }
            vec.push_back(arr[i]);
        }
    }
    if(vec.empty()){
        puts("0");
        return;
    }
    for(int i=0; i<(int)vec.size(); i++){
        for(int j=i+1; j<(int)vec.size(); j++){
//            Frac tmp = ccw(vec[i], vec[j], point);
//            printf("%lld %lld %d\n", tmp.a, tmp.b, tmp == 0);
            if(ccw(vec[i], vec[j], point) == 0 && ((vec[i] < point) ^ (vec[j] < point))){
                puts("2");
                return;
            }
        }
    }

    vec.push_back(point);
    vec = hull(vec);
    if(inside(vec, point)) puts("3");
    else puts("0");
}

int main(){
    input(point);
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        char c;
        scanf(" %c", &c);
        if(c == 'A') input(arr[++arrSize]);
        else{
            int x;
            scanf("%d", &x);
            deleted[x] = 1;
        }
        calc();
    }
}

Compilation message

Mixture.cpp: In function 'void input(vector2&)':
Mixture.cpp:93:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |     scanf("%d %d %d", &a, &b, &c);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Mixture.cpp: In function 'int main()':
Mixture.cpp:159:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  159 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
Mixture.cpp:162:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  162 |         scanf(" %c", &c);
      |         ~~~~~^~~~~~~~~~~
Mixture.cpp:166:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  166 |             scanf("%d", &x);
      |             ~~~~~^~~~~~~~~~

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 3 ms 212 KB Output is correct
7 Correct 12 ms 316 KB Output is correct
8 Correct 2 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 6 ms 212 KB Output is correct
17 Correct 7 ms 312 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 3 ms 212 KB Output is correct
7 Correct 12 ms 316 KB Output is correct
8 Correct 2 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 6 ms 212 KB Output is correct
17 Correct 7 ms 312 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 10 ms 316 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 830 ms 320 KB Output is correct
23 Correct 101 ms 340 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 10 ms 340 KB Output is correct
26 Correct 4 ms 340 KB Output is correct
27 Correct 1164 ms 316 KB Output is correct
28 Execution timed out 2082 ms 436 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 3 ms 212 KB Output is correct
7 Correct 12 ms 316 KB Output is correct
8 Correct 2 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 6 ms 212 KB Output is correct
17 Correct 7 ms 312 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 10 ms 316 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 830 ms 320 KB Output is correct
23 Correct 101 ms 340 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 10 ms 340 KB Output is correct
26 Correct 4 ms 340 KB Output is correct
27 Correct 1164 ms 316 KB Output is correct
28 Execution timed out 2082 ms 436 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 3 ms 212 KB Output is correct
7 Correct 12 ms 316 KB Output is correct
8 Correct 2 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 6 ms 212 KB Output is correct
17 Correct 7 ms 312 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 10 ms 316 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 830 ms 320 KB Output is correct
23 Correct 101 ms 340 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 10 ms 340 KB Output is correct
26 Correct 4 ms 340 KB Output is correct
27 Correct 1164 ms 316 KB Output is correct
28 Execution timed out 2082 ms 436 KB Time limit exceeded
29 Halted 0 ms 0 KB -