oj.uz

Submission #587010

# Submission time Handle Problem Language Result Execution time Memory
587010 2022-07-01T08:08:26 Z 반딧불(#8396) Mixture (BOI20_mixture) C++17
13 / 100
 3 ms 340 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);
}

long long 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; /// 180�� �ʰ��� ������ ���°�?

bool large(vector2 a, vector2 b){
    return ccw(a, vector2(0, 0), b) > 0;
}

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 addPoint(){
    long long 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]]++;
    threeCnt = calc3();
    return;

    if((int)threeMp.size() < 2){
        threeMp[arr[i]]++;
        if((int)threeMp.size() == 2 && twoCnt) threeCnt = 1;
        else threeCnt = 0;
        return;
    }
    if(threeMp.find(arr[i]) != threeMp.end() || threeCnt){
        threeMp[arr[i]]++;
        return;
    }

    auto it = threeMp.lower_bound(arr[i]);
    bool delOrig = 0;
    if(it == threeMp.begin()) delOrig = large(threeMp.rbegin()->first, threeMp.begin()->first);
    else delOrig = large(prev(it)->first, it->first);
    if(delOrig) threeCnt = 1;

    threeMp[arr[i]]++;
//    for(auto p: threeMp) printf("(%lld, %lld) ", p.first.x, p.first.y);
//    puts("");
    it = threeMp.lower_bound(arr[i]);
    assert(it != threeMp.end());
    bool newOrig = 0;
    if(it == prev(threeMp.end())) newOrig |= large(it->first, threeMp.begin()->first);
    else newOrig |= large(it->first, next(it)->first);
    if(it == threeMp.begin()) newOrig |= large(threeMp.rbegin()->first, it->first);
    else newOrig |= large(prev(it)->first, it->first);
    if(newOrig) threeCnt = 0;
}

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]);
//    threeCnt = calc3();
//    return;

    if((int)threeMp.size() <= 2){
        threeMp[arr[i]]--;
        if(!threeMp[arr[i]]) threeMp.erase(arr[i]);
        if((int)threeMp.size() == 2 && twoCnt) threeCnt = 1;
        else threeCnt = 0;
        return;
    }
    if(threeMp[arr[i]] > 1 || !threeCnt){
        threeMp[arr[i]]--;
        return;
    }

    threeMp.erase(arr[i]);

    if((int)threeMp.size() == 2 && twoCnt){
        threeCnt = 1;
        return;
    }

    auto it = threeMp.lower_bound(arr[i]);
    bool newOrig = 0;
    if(it == threeMp.begin() || it == threeMp.end()) newOrig = large(threeMp.rbegin()->first, threeMp.begin()->first);
    else newOrig = large(prev(it)->first, it->first);
    if(newOrig) threeCnt = 0;
}

void print(){
    if(oneCnt) puts("1");
    else if(twoCnt) puts("2");
    else if(threeCnt) 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:98:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |     scanf("%lld %lld %lld", &x, &y, &z);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Mixture.cpp: In function 'void delPoint()':
Mixture.cpp:149:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  149 |     scanf("%d", &i);
      |     ~~~~~^~~~~~~~~~
Mixture.cpp: In function 'int main()':
Mixture.cpp:201:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  201 |     scanf("%lld %lld %lld %d", &A, &B, &C, &n);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Mixture.cpp:204:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  204 |         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:82:13: note: 'prv.vector2::x' was declared here
   82 |     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:82:13: note: 'prv.vector2::y' was declared here
   82 |     vector2 prv;
      |             ^~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 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 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 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 1 ms 212 KB Output is correct
17 Correct 1 ms 212 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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 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 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 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 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 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 2 ms 340 KB Output is correct
24 Correct 1 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 320 KB Output is correct
28 Correct 1 ms 212 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 212 KB Output is correct
32 Correct 3 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 Incorrect 1 ms 340 KB Output isn't correct
37 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 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 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 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 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 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 2 ms 340 KB Output is correct
24 Correct 1 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 320 KB Output is correct
28 Correct 1 ms 212 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 212 KB Output is correct
32 Correct 3 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 Incorrect 1 ms 340 KB Output isn't correct
37 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 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 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 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 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 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 2 ms 340 KB Output is correct
24 Correct 1 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 320 KB Output is correct
28 Correct 1 ms 212 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 212 KB Output is correct
32 Correct 3 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 Incorrect 1 ms 340 KB Output isn't correct
37 Halted 0 ms 0 KB -