oj.uz

Submission #586980

# Submission time Handle Problem Language Result Execution time Memory
586980 2022-07-01T07:14:34 Z 반딧불(#8396) Mixture (BOI20_mixture) C++17
0 / 100
 1 ms 212 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef TEST
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(ll(0), ll(0))) ^ (make_pair(r.y, r.x) > make_pair(ll(0), ll(0)))){
            return make_pair(y, x) > make_pair(ll(0), ll(0));
        }
        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);
}

ll mabs(ll x){
    return x>=0?x:-x;
}

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 = mabs(__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:79:15: warning: format '%lld' expects argument of type 'long long int*', but argument 2 has type 'll*' {aka '__int128*'} [-Wformat=]
   79 |     scanf("%lld %lld %lld", &x, &y, &z);
      |            ~~~^             ~~
      |               |             |
      |               |             ll* {aka __int128*}
      |               long long int*
Mixture.cpp:79:20: warning: format '%lld' expects argument of type 'long long int*', but argument 3 has type 'll*' {aka '__int128*'} [-Wformat=]
   79 |     scanf("%lld %lld %lld", &x, &y, &z);
      |                 ~~~^            ~~
      |                    |            |
      |                    |            ll* {aka __int128*}
      |                    long long int*
Mixture.cpp:79:25: warning: format '%lld' expects argument of type 'long long int*', but argument 4 has type 'll*' {aka '__int128*'} [-Wformat=]
   79 |     scanf("%lld %lld %lld", &x, &y, &z);
      |                      ~~~^           ~~
      |                         |           |
      |                         |           ll* {aka __int128*}
      |                         long long int*
Mixture.cpp: In function 'int main()':
Mixture.cpp:140:15: warning: format '%lld' expects argument of type 'long long int*', but argument 2 has type 'll*' {aka '__int128*'} [-Wformat=]
  140 |     scanf("%lld %lld %lld %d", &A, &B, &C, &n);
      |            ~~~^                ~~
      |               |                |
      |               long long int*   ll* {aka __int128*}
Mixture.cpp:140:20: warning: format '%lld' expects argument of type 'long long int*', but argument 3 has type 'll*' {aka '__int128*'} [-Wformat=]
  140 |     scanf("%lld %lld %lld %d", &A, &B, &C, &n);
      |                 ~~~^               ~~
      |                    |               |
      |                    long long int*  ll* {aka __int128*}
Mixture.cpp:140:25: warning: format '%lld' expects argument of type 'long long int*', but argument 4 has type 'll*' {aka '__int128*'} [-Wformat=]
  140 |     scanf("%lld %lld %lld %d", &A, &B, &C, &n);
      |                      ~~~^              ~~
      |                         |              |
      |                         long long int* ll* {aka __int128*}
Mixture.cpp: In function 'void addPoint()':
Mixture.cpp:79:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |     scanf("%lld %lld %lld", &x, &y, &z);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Mixture.cpp: In function 'void delPoint()':
Mixture.cpp:100:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |     scanf("%d", &i);
      |     ~~~~~^~~~~~~~~~
Mixture.cpp: In function 'int main()':
Mixture.cpp:140:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  140 |     scanf("%lld %lld %lld %d", &A, &B, &C, &n);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Mixture.cpp:143:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  143 |         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:118:13: note: 'prv.vector2::x' was declared here
  118 |     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:118:13: note: 'prv.vector2::y' was declared here
  118 |     vector2 prv;
      |             ^~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -