oj.uz

Submission #586973

# Submission time Handle Problem Language Result Execution time Memory
586973 2022-07-01T07:09:21 Z 반딧불(#8396) Mixture (BOI20_mixture) C++17
60 / 100
 60 ms 1096 KB 
#include <bits/stdc++.h>

using namespace std;

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

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

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

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

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

    bool operator<(const vector2 &r)const{
        if((make_pair(y, x) > make_pair(0LL, 0LL)) ^ (make_pair(r.y, r.x) > make_pair(0LL, 0LL))){
            return make_pair(y, x) > make_pair(0LL, 0LL);
        }
        return (vector2(0, 0) - *this).cross(r - *this) < 0;
    }

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

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

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

vector2 calc(ll A, ll B, ll C, ll x, ll y, ll z){
    C += A+B, z += x+y;
    A*=z, B*=z, x*=C, y*=C;
    x-=A, y-=B;
    ll g = abs(__gcd(x, y));
    if(g) x/=g, y/=g;
    return vector2(x, y);
}

ll A, B, C;
int n;
vector2 arr[100002];
int arrCnt;

/// ans=1 ���
int oneCnt;

/// ans=2 ���
map<vector2, ll> twoMp;
ll twoCnt;

/// ans=3 ���
map<vector2, int> threeMp;
bool threeCnt;

void addPoint(){
    ll x, y, z;
    scanf("%lld %lld %lld", &x, &y, &z);
    int i = ++arrCnt;
    arr[i] = calc(A, B, C, x, y, z);

    /// ans=1 update
    if(arr[i] == vector2(0, 0)){
        oneCnt++;
        return;
    }

    /// ans=2 update
    twoMp[arr[i]]++;
    twoCnt += twoMp[-arr[i]];

    /// ans=3 update
    threeMp[arr[i]]++;
//    auto it = threeMp.lower_bound(arr[i]);
}

void delPoint(){
    int i;
    scanf("%d", &i);

    /// ans=1 update
    if(arr[i] == vector2(0, 0)){
        oneCnt--;
        return;
    }

    /// ans=2 update
    twoCnt -= twoMp[-arr[i]];
    twoMp[arr[i]]--;

    /// ans=3 update
    threeMp[arr[i]]--;
    if(!threeMp[arr[i]]) threeMp.erase(arr[i]);
}

bool calc3(){
    vector2 prv;
    if(threeMp.size() <= 2) return false;
    for(auto it = threeMp.begin(); it != threeMp.end(); ++it){
        if(it == threeMp.begin()){
            prv = it->first;
            continue;
        }
        if(ccw(prv, vector2(0, 0), it->first) >= 0) return false;
        prv = it->first;
    }
    if(ccw(prv, vector2(0, 0), threeMp.begin()->first) >= 0) return false;
    return true;
}

void print(){
    if(oneCnt) puts("1");
    else if(twoCnt) puts("2");
    else if(calc3()) puts("3");
    else puts("0");
}

int main(){
    scanf("%lld %lld %lld %d", &A, &B, &C, &n);
    for(int i=1; i<=n; i++){
        char c;
        scanf(" %c", &c);
        if(c=='A') addPoint();
        else delPoint();
        print();
    }
}

Compilation message

Mixture.cpp: In function 'void addPoint()':
Mixture.cpp:75:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |     scanf("%lld %lld %lld", &x, &y, &z);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Mixture.cpp: In function 'void delPoint()':
Mixture.cpp:96:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |     scanf("%d", &i);
      |     ~~~~~^~~~~~~~~~
Mixture.cpp: In function 'int main()':
Mixture.cpp:136:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |     scanf("%lld %lld %lld %d", &A, &B, &C, &n);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Mixture.cpp:139:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  139 |         scanf(" %c", &c);
      |         ~~~~~^~~~~~~~~~~
Mixture.cpp: In function 'bool calc3()':
Mixture.cpp:21:36: warning: 'prv.vector2::x' may be used uninitialized in this function [-Wmaybe-uninitialized]
   21 |         return vector2(x-r.x, y-r.y);
      |                                    ^
Mixture.cpp:114:13: note: 'prv.vector2::x' was declared here
  114 |     vector2 prv;
      |             ^~~
Mixture.cpp:21:36: warning: 'prv.vector2::y' may be used uninitialized in this function [-Wmaybe-uninitialized]
   21 |         return vector2(x-r.x, y-r.y);
      |                                    ^
Mixture.cpp:114:13: note: 'prv.vector2::y' was declared here
  114 |     vector2 prv;
      |             ^~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 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 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 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 260 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 324 KB Output is correct
19 Correct 0 ms 212 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 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 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 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 260 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 324 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 1 ms 212 KB Output is correct
27 Correct 1 ms 212 KB Output is correct
28 Correct 1 ms 212 KB Output is correct
29 Correct 1 ms 308 KB Output is correct
30 Correct 1 ms 304 KB Output is correct
31 Correct 1 ms 440 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 212 KB Output is correct
34 Correct 2 ms 340 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 1 ms 340 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 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 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 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 260 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 324 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 1 ms 212 KB Output is correct
27 Correct 1 ms 212 KB Output is correct
28 Correct 1 ms 212 KB Output is correct
29 Correct 1 ms 308 KB Output is correct
30 Correct 1 ms 304 KB Output is correct
31 Correct 1 ms 440 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 212 KB Output is correct
34 Correct 2 ms 340 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 1 ms 340 KB Output is correct
37 Correct 1 ms 312 KB Output is correct
38 Correct 1 ms 340 KB Output is correct
39 Correct 1 ms 340 KB Output is correct
40 Correct 3 ms 340 KB Output is correct
41 Correct 4 ms 340 KB Output is correct
42 Correct 3 ms 340 KB Output is correct
43 Correct 2 ms 444 KB Output is correct
44 Correct 2 ms 468 KB Output is correct
45 Correct 3 ms 468 KB Output is correct
46 Correct 4 ms 596 KB Output is correct
47 Correct 15 ms 692 KB Output is correct
48 Correct 2 ms 320 KB Output is correct
49 Correct 3 ms 340 KB Output is correct
50 Correct 3 ms 340 KB Output is correct
51 Correct 43 ms 712 KB Output is correct
52 Correct 3 ms 496 KB Output is correct
53 Correct 60 ms 704 KB Output is correct
54 Correct 58 ms 720 KB Output is correct
55 Correct 3 ms 340 KB Output is correct
56 Correct 3 ms 320 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 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 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 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 260 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 324 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 1 ms 212 KB Output is correct
27 Correct 1 ms 212 KB Output is correct
28 Correct 1 ms 212 KB Output is correct
29 Correct 1 ms 308 KB Output is correct
30 Correct 1 ms 304 KB Output is correct
31 Correct 1 ms 440 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 212 KB Output is correct
34 Correct 2 ms 340 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 1 ms 340 KB Output is correct
37 Correct 1 ms 312 KB Output is correct
38 Correct 1 ms 340 KB Output is correct
39 Correct 1 ms 340 KB Output is correct
40 Correct 3 ms 340 KB Output is correct
41 Correct 4 ms 340 KB Output is correct
42 Correct 3 ms 340 KB Output is correct
43 Correct 2 ms 444 KB Output is correct
44 Correct 2 ms 468 KB Output is correct
45 Correct 3 ms 468 KB Output is correct
46 Correct 4 ms 596 KB Output is correct
47 Correct 15 ms 692 KB Output is correct
48 Correct 2 ms 320 KB Output is correct
49 Correct 3 ms 340 KB Output is correct
50 Correct 3 ms 340 KB Output is correct
51 Correct 43 ms 712 KB Output is correct
52 Correct 3 ms 496 KB Output is correct
53 Correct 60 ms 704 KB Output is correct
54 Correct 58 ms 720 KB Output is correct
55 Correct 3 ms 340 KB Output is correct
56 Correct 3 ms 320 KB Output is correct
57 Correct 3 ms 448 KB Output is correct
58 Correct 49 ms 1036 KB Output is correct
59 Incorrect 19 ms 1096 KB Output isn't correct
60 Halted 0 ms 0 KB -