oj.uz

Submission #530591

# Submission time Handle Problem Language Result Execution time Memory
530591 2022-02-25T23:54:05 Z c28dnv9q3 Mixture (BOI20_mixture) C++17
0 / 100
 1 ms 296 KB 
#include <iostream>
#include <bits/stdc++.h>
#define lli long long int
#define RBit _Rb_tree_iterator<pair<const pair<lli, lli>, int>>

using namespace std;

lli a, b, c;
static lli t = 0;

lli ggt(lli a, lli b) {
    return a == 0 ? b : ggt(b % a, a);
}

pair<lli, lli> toPoint(lli tX, lli tY, lli tZ) {
    lli x, y, z;
    if (a != 0) {
        x = tY * a - tX * b; y = tZ * a - tX * c;
    } else if (b != 0) {
        x = tX * b - tY * a; y = tZ * b - tY * c;
    } else {
        x = tX * c - tZ * a; y = tY * c - tZ * b;
    }
    lli d = abs(ggt(x, y));
    if (d == 0) return pair<lli, lli>(0, 0);
    x /= d;
    y /= d;
    return pair<lli, lli>(x, y);
}

pair<lli, lli> inverse(pair<lli, lli> p) {
    return pair<lli, lli>(- p.first, - p.second);
}

struct cmp {
    bool operator()(const pair<lli, lli>& a, const pair<lli, lli>& b) const {
        if (a.first >= 0 && b.first < 0) return true;
        if (b.first >= 0 && a.first < 0) return false;
        return a.second * b.first > b.second * a.first;
    }
};

bool operator < (pair<lli, lli>& a, pair<lli, lli>& b) {
    if (a.first >= 0 && b.first < 0) return true;
    if (b.first >= 0 && a.first < 0) return false;
    return a.second * b.first >= b.second * a.first;
}

ostream& operator << (ostream& io, const pair<lli, lli>& p) {
    io << p.first << " " << p.second;
    return io;
}

ostream& operator << (ostream& io, const pair<pair<lli, lli>, int>& p) {
    io << p.first << " x " << p.second << "\n";
    return io;
}

bool okay(map<pair<lli, lli>, int, cmp> circle) {
    if (circle.size() == 0) return false;
    RBit it = circle.begin();
    RBit inv = circle.upper_bound(inverse((*it).first));
    if (circle.end() == inv) inv = circle.begin();
    RBit invinv = circle.upper_bound(inverse((*inv).first));
    if (circle.end() == invinv) invinv = circle.begin();
    return it != inv && inv != invinv;
}

int main() {
    cin >> a >> b >> c;

    int n, d;
    bool t;
    pair<lli, lli> p, inv;
    vector<pair<lli, lli>> regal;
    map<pair<lli, lli>, int, cmp> circle;

    int q;
    cin >> q;

    string inst;
    int pos;

    lli x, y, z;

    for (int i = 0; i < q; ++i) {
        //cout << i << "\n";

        cin >> inst;

        if (inst == "A") {
            cin >> x >> y >> z;
            p = toPoint(x, y, z);
            inv = inverse(p);

            /*
            cout << "\n";
            cout << x << " " << y << " " << z << "\n";
            cout << p;
            cout << "\n\n";
             */

            /*
            cout << "adding\n";
            cout << p;
            cout << "\n";
             */

            if ((*circle.find(p)).first == p && (*circle.find(inv)).first == inv) d--;

            regal.push_back(p);
            if (p.first == 0 && p.second == 0) n++; else {
                circle[p]++;
            }

            /*
            cout << "dtest\n";
            cout << *circle.end();
            cout << circle[p] << "\n";
            cout << *circle.find(p);
            cout << p << "\n";
            cout << *circle.find(inv);
            cout << inv << "\n";
             */

            if ((*circle.find(p)).first == p && (*circle.find(inv)).first == inv) d++;
        }

        if (inst == "R") {
            cin >> pos;
            p = regal[pos - 1];
            inv = inverse(p);

            if ((*circle.find(p)).first == p && (*circle.find(inv)).first == inv) d--;

            if (p.first == 0 && p.second == 0) n--; else {
                circle[p]--;
                if (circle[p] == 0) circle.erase(p);
            }

            if ((*circle.find(p)).first == p && (*circle.find(inv)).first == inv) d++;
        }

        /*
        cout << "0 0 x " << n << "\n";
        for (pair<pair<lli, lli>, int> j: circle) cout << j;
        cout << "\n";
         */

        if (n > 0) {
            cout << 1;
        } else {
            if (d > 0) {
                cout << 2;
            } else {
                if (okay(circle)) {
                    cout << 3;
                } else {
                    cout << 0;
                }
            }
        }
        cout << "\n";
    }
}

Compilation message

Mixture.cpp: In function 'std::pair<long long int, long long int> toPoint(long long int, long long int, long long int)':
Mixture.cpp:16:15: warning: unused variable 'z' [-Wunused-variable]
   16 |     lli x, y, z;
      |               ^
Mixture.cpp: In function 'int main()':
Mixture.cpp:73:10: warning: unused variable 't' [-Wunused-variable]
   73 |     bool t;
      |          ^
Mixture.cpp: At global scope:
Mixture.cpp:9:12: warning: 't' defined but not used [-Wunused-variable]
    9 | static lli t = 0;
      |            ^
Mixture.cpp: In function 'int main()':
Mixture.cpp:109:84: warning: 'd' may be used uninitialized in this function [-Wmaybe-uninitialized]
  109 |             if ((*circle.find(p)).first == p && (*circle.find(inv)).first == inv) d--;
      |                                                                                   ~^~
Mixture.cpp:112:49: warning: 'n' may be used uninitialized in this function [-Wmaybe-uninitialized]
  112 |             if (p.first == 0 && p.second == 0) n++; else {
      |                                                ~^~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 296 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 296 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 296 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 296 KB Output isn't correct
2 Halted 0 ms 0 KB -