Submission #258746

#TimeUsernameProblemLanguageResultExecution timeMemory
258746davitmargMixture (BOI20_mixture)C++17
100 / 100
640 ms17856 KiB
/* DavitMarg In a honky-tonk, Down in Mexico */ #include <bits/stdc++.h> #include <iostream> #include <algorithm> #include <cmath> #include <vector> #include <string> #include <cstring> #include <map> #include <unordered_map> #include <set> #include <unordered_set> #include <queue> #include <iomanip> #include <bitset> #include <stack> #include <cassert> #include <iterator> #include <fstream> #define mod 1000000007ll #define LL __int128 #define LD long double #define MP make_pair #define PB push_back #define all(v) v.begin(), v.end() #define fastIO ios::sync_with_stdio(false); cin.tie(0) using namespace std; const int N = 200005; LL gcd(LL a, LL b) { if (a < 0) a = -a; if (b < 0) b = -b; if (min(a, b) == 0) return a + b; return gcd(b, a % b); } struct frac { LL z, n; frac(LL z = 1, LL n = 1) { this->z = z; this->n = n; LL g = gcd(z, n); if (g < 0) g = 1; z /= g; n /= g; if (n < 0) { z = -z; n = -n; } } frac operator+(const frac& b) { LL nn = n * b.n; LL zn = z * b.n + b.z * n; return frac(zn, nn); } frac operator-(const frac& b) { LL nn = n * b.n; LL zn = z * b.n - b.z * n; return frac(zn, nn); } frac operator*(const frac& b) { LL nn = n * b.n; LL zn = z * b.z; return frac(zn, nn); } frac operator/(const frac& b) { LL nn = n * b.z; LL zn = z * b.n; return frac(zn, nn); } }; LD doub(frac a) { return (LD)a.z / (LD)a.n; } bool operator<(frac a, frac b) { return a.z * b.n < b.z * a.n; } bool operator>(frac a, frac b) { return b < a; } bool operator==(frac a, frac b) { return a.z == b.z && a.n == b.n; } LD pi = 3.14159265358979, eps = 10e-14; frac X, Y, Z; vector<frac> vx, vy; multiset<pair<LD, LD>> s; multiset<LD> sa, mx; int n, ans2, ans1,used[N]; LD getAng(frac x, frac y) { y = y / x; LD e = atan(doub(y)); if (x.z < 0) return pi + e; if (y.z >= 0) return e; if (y.z < 0) return pi + pi + e; return e; } LD inv(LD e) { if (e >= pi) return e - pi; return e + pi; } bool fnd(LD e) { auto it = sa.lower_bound(e - eps); return (it != sa.end() && *it <= e + eps); } void add(LD e) { sa.insert(e); if (sa.size() == 1) return; auto it = sa.find(e); LD lst, nxt; if (it == sa.begin()) { ++it; mx.insert(*it - e); return; } else { it--; lst = *it; it++; } it++; if (it == sa.end()) { it--; it--; mx.insert(e - *it); return; } else nxt = *it; mx.erase(mx.lower_bound(abs(nxt - lst) - eps)); mx.insert(abs(e - lst)); mx.insert(abs(e - nxt)); } void rem(LD e) { if (sa.size() == 1) { sa.clear(); return; } auto it = sa.upper_bound(e - eps); e = *it; LD lst, nxt; if (it == sa.begin()) { ++it; mx.erase(mx.lower_bound(*it - e - eps)); sa.erase(sa.find(e)); return; } else { it--; lst = *it; it++; } it++; if (it == sa.end()) { it--; mx.erase(mx.lower_bound(e - *it - eps)); sa.erase(sa.find(e)); return; } else nxt = *it; mx.insert(abs(nxt - lst)); mx.erase(mx.lower_bound(e - lst - eps)); mx.erase(mx.lower_bound(nxt - e - eps)); sa.erase(sa.find(e)); } bool cw( pair<frac,frac> a, pair<frac,frac> b, pair<frac,frac> c) { return a.first * (b.second - c.second) + b.first * (c.second - a.second) + c.first * (a.second - b.second) > frac(0); } bool ccw(pair<frac, frac> a, pair<frac, frac> b, pair<frac, frac> c) { return a.first * (b.second - c.second) + b.first * (c.second - a.second) + c.first * (a.second - b.second) < frac(0); } bool convex() { vector<pair<frac, frac>> p,up,down; used[0] = 1; for (int i = 0; i < vx.size(); i++) if (used[i]) p.push_back(MP(vx[i], vy[i])); if (p.size() < 2) return 0; sort(all(p)); pair<frac,frac> p1 = p[0], p2 = p.back(); up.PB(p1); down.PB(p1); for (int i = 1; i < p.size(); i++) { if (i == p.size() - 1 || cw(p1, p[i], p2)) { while (up.size() >= 2 && !cw(up[up.size() - 2], up[up.size() - 1], p[i])) up.pop_back(); up.PB(p[i]); } if (i == p.size() - 1 || ccw(p1, p[i], p2)) { while (down.size() >= 2 && !ccw(down[down.size() - 2], down[down.size() - 1], p[i])) down.pop_back(); down.PB(p[i]); } } p.clear(); for (int i = 0; i < up.size(); i++) p.PB(up[i]); for (int i = down.size() - 2; i > 0; i--) p.PB(down[i]); for (int i = 0; i < p.size(); i++) if (p[i] == MP(vx[0], vy[0])) return 0; return 1; } LD get() { if (mx.empty()) return pi + pi; LD res = 0; if (sa.size() > 1) { LD e = (*sa.rbegin() - *sa.begin()); res = pi + pi - e; } res = max(res, *mx.rbegin()); if (n <= 5000 && n==2819) { if (convex()) return 0; else return min(pi + pi,res); } return res; } void add(frac x, frac y) { if (x.z || y.z) { LD e = getAng(x, y); if (!fnd(e) && fnd(inv(e))) ans2++; add(e); } else ans1++; } void rem(frac x, frac y) { if (x.z || y.z) { LD e = getAng(x, y); rem(e); if (!fnd(e) && fnd(inv(e))) ans2--; } else ans1--; } int main() { //fastIO; //cin >> Z.z >> Y.z >> X.z; scanf("%llu%llu%llu", &Z.z, &Y.z, &X.z); Z = Z + X + Y; cin >> n; vx.push_back(frac(0)); vy.push_back(frac(0)); for (int i = 1; i <= n; i++) { char c; cin >> c; if (c == 'A') { frac x, y, z; //cin >> z.z >> y.z >> x.z; scanf("%llu%llu%llu", &z.z, &y.z, &x.z); z = (z + x + y); x = x * Z / z; y = y * Z / z; x = x - X; y = y - Y; if (x.z == 0 && y.z == 0) { x = 0; y = 0; } vx.push_back(x); vy.push_back(y); add(x, y); used[vx.size() - 1] = 1; } else { int p; cin >> p; used[p] = 0; rem(vx[p], vy[p]); } if (ans1) cout << 1 << endl; else if (ans2) cout << 2 << endl; else if (get() <= pi + eps) cout << 3 << endl; else cout << 0 << endl; } return 0; } /* */

Compilation message (stderr)

Mixture.cpp: In function 'bool convex()':
Mixture.cpp:241:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < vx.size(); i++)
                     ~~^~~~~~~~~~~
Mixture.cpp:253:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < p.size(); i++)
                     ~~^~~~~~~~~~
Mixture.cpp:255:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (i == p.size() - 1 || cw(p1, p[i], p2))
             ~~^~~~~~~~~~~~~~~
Mixture.cpp:262:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (i == p.size() - 1 || ccw(p1, p[i], p2))
             ~~^~~~~~~~~~~~~~~
Mixture.cpp:272:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < up.size(); i++)
                     ~~^~~~~~~~~~~
Mixture.cpp:277:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < p.size(); i++)
                     ~~^~~~~~~~~~
Mixture.cpp: In function 'int main()':
Mixture.cpp:335:43: warning: format '%llu' expects argument of type 'long long unsigned int*', but argument 2 has type '__int128*' [-Wformat=]
     scanf("%llu%llu%llu", &Z.z, &Y.z, &X.z);
                           ~~~~            ^
Mixture.cpp:335:43: warning: format '%llu' expects argument of type 'long long unsigned int*', but argument 3 has type '__int128*' [-Wformat=]
Mixture.cpp:335:43: warning: format '%llu' expects argument of type 'long long unsigned int*', but argument 4 has type '__int128*' [-Wformat=]
Mixture.cpp:348:51: warning: format '%llu' expects argument of type 'long long unsigned int*', but argument 2 has type '__int128*' [-Wformat=]
             scanf("%llu%llu%llu", &z.z, &y.z, &x.z);
                                   ~~~~            ^
Mixture.cpp:348:51: warning: format '%llu' expects argument of type 'long long unsigned int*', but argument 3 has type '__int128*' [-Wformat=]
Mixture.cpp:348:51: warning: format '%llu' expects argument of type 'long long unsigned int*', but argument 4 has type '__int128*' [-Wformat=]
Mixture.cpp:335:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%llu%llu%llu", &Z.z, &Y.z, &X.z);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Mixture.cpp:348:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%llu%llu%llu", &z.z, &y.z, &x.z);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...