제출 #1263142

#제출 시각아이디문제언어결과실행 시간메모리
1263142M_W_13Mixture (BOI20_mixture)C++20
60 / 100
16 ms1652 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; #define rep(i, n) for (int i = 0; i < (n); i++) #define st first #define nd second #define pb push_back #define wsp pair<pair<ll, ll>, ll> const int MAXN = 1e5 + 7; vector<wsp> vec; vector<pair<pair<ll, ll>, int>> pom; map <pair<ll, ll>, int> ile; set<pair<int, int>> S; map<int, int> jaki; wsp T[MAXN]; int pol = 0; int lic = 0; ll a, b, c; map<wsp, int> Sile; bool dod(pair<ll, ll> p) { // cout << p.st << " " << p.nd << '\n'; ile[p]++; if (ile[p] == 1) { if (ile[{-p.st, -p.nd}] >= 1) { pol++; } } if (pol > 0) { return true; } return false; } bool odejm(pair<ll, ll> p) { if (ile[p] == 1) { if (ile[{-p.st, -p.nd}] >= 1) { pol--; } } ile[p]--; if (pol > 0) { return true; } return false; } bool spr1() { if (ile[{0, 0}] > 0) { return true; } return false; } void wypisz(pair<ll, ll> p) { cout << p.st << " " << p.nd << " "; } pair<ll, ll> przemien(wsp p) { ll x = p.st.st; ll y = p.st.nd; ll z = p.nd; // cout << "x = " << x << " y = " << y << " z = " << z << '\n'; ll X = x * c - a * z; ll Y = y * c - b * z; // if (z == 0 || Y == 0) { // cout << "XDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD" << '\n'; // } if (z == 0) { X = x; Y = y; } ll d = __gcd(abs(X), abs(Y)); if (d != 0) { X /= d; Y /= d; } // cout << "X = " << X << " Y = " << Y << '\n'; return {X, Y}; } pair<int, ld> zmiana(pair<ld, ld> p) { ld t1 = p.st/p.nd; if (p.nd == 0) { if (p.st < 0) { return {2, t1}; } return {5, t1}; } if (p.nd < 0) { if (p.st < 0) { return {1, t1}; } return {0, t1}; } if (p.st > 0) { return {4, t1}; } return {3, t1}; } bool por(pair<pair<ld, ld>, int> x2, pair<pair<ld, ld>, int> y2) { pair<ld, ld> x = x2.st; pair<ld, ld> y = y2.st; if (zmiana(x).st == zmiana(y).st) { __int128_t a = x.st; __int128_t b = x.nd; __int128_t c = y.st; __int128_t d = y.nd; return ((a * d) > (b * c)); } return zmiana(x) > zmiana(y); } void przesort() { int sz = vec.size(); // cout << "szzzzzzzzzzzzzzzzz = " << sz << '\n'; rep(i, sz) { pom.pb({przemien(vec[i]), i}); } sort(pom.begin(), pom.end(), por); int kt = 1; // cout << "SORT" << '\n'; for (auto p: pom) { jaki[p.nd] = kt; // cout << "kt = " << kt << " "; pair<ll, ll> paraa = przemien(T[kt]); // wypisz(paraa); // cout << '\n'; // ld a = paraa.st; // ld b = paraa.nd; // ld c = a/b; // cout << zmiana({a, b}) << '\n'; // cout << c << '\n'; kt++; } } bool czytak(pair<ll, ll> p1, pair<ll, ll> p2) { if ((p1.st * p2.nd - p2.st * p1.nd) < 0) { return true; } return false; } bool patrz(wsp p, int kt) { // cout << "HHH" << endl; int nr = jaki[kt]; S.insert({nr, kt}); auto it = S.upper_bound({nr, kt}); auto it2 = S.lower_bound({nr, kt}); // cout << "t11" << endl; if (it2 == S.begin()) { it2 = S.end(); } // cout << "PR" << endl; it2--; if (it == S.end()) { it = S.begin(); } // cout << "XDD" << endl; int ktlast = (*it2).nd; int nrlast = (*it2).st; int ktnxt = (*it).nd; int nrnxt = (*it).st; pair<ll, ll> plast = przemien(T[ktlast]); pair<ll, ll> pnxt = przemien(T[ktnxt]); pair<ll, ll> pter = przemien(T[kt]); if (czytak(plast, pnxt) || (plast == pnxt && nrlast >= nrnxt)) { // cout << "ODEEEEJM = "; // wypisz(plast); // wypisz(pnxt); // cout << '\n'; lic--; } if (czytak(plast, pter) || (plast == pter && nrlast >= nr)) { // cout << "DZIAAAALAAAA = "; // wypisz(plast); // wypisz(pter); // cout << '\n'; lic++; } if (czytak(pter, pnxt) || (pter == pnxt && nr >= nrnxt)) { // cout << "DZIAAAALAAAA = "; // wypisz(pter); // wypisz(pnxt); // cout << '\n'; lic++; } if (lic == 0) { return true; } return false; } bool patrz2(wsp p, int kt) { int nr = jaki[kt]; // cout << "XD" << endl; S.erase({nr, kt}); // cout << "XD2" << endl; if ((int)S.size() == 0) { lic = 0; return false; } auto it = S.upper_bound({nr, kt}); auto it2 = S.lower_bound({nr, kt}); // cout << "XD3" << endl; if (it2 == S.begin()) { it2 = S.end(); } it2--; if (it == S.end()) { it = S.begin(); } int ktlast = (*it2).nd; int nrlast = (*it2).st; int ktnxt = (*it).nd; int nrnxt = (*it).st; pair<ll, ll> plast = przemien(T[ktlast]); pair<ll, ll> pnxt = przemien(T[ktnxt]); pair<ll, ll> pter = przemien(T[kt]); if (czytak(plast, pnxt) || (plast == pnxt && nrlast >= nrnxt)) { lic++; } if (czytak(plast, pter) || (plast == pter && nrlast >= nr)) { lic--; } if (czytak(pter, pnxt) || (pter == pnxt && nr >= nrnxt)) { lic--; } if (lic == 0) { return true; } return false; } struct upd { int typ; ll x, y, z; }; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout << fixed << setprecision(10); cin >> a >> b >> c; int liccccc = 0; while (c == 0) { liccccc++; swap(a, c); swap(b, c); } ll nwdd = __gcd(a, __gcd(b, c)); a /= nwdd; b /= nwdd; c /= nwdd; vector<upd> zm; int q; cin >> q; int ktor = 0; rep(i, q) { char s; cin >> s; if (s == 'A') { ll x, y, z; cin >> x >> y >> z; // cout << "x = " << x << " y = " << y << " z = " << z << '\n'; rep(cos, liccccc) { swap(x, z); swap(y, z); } nwdd = __gcd(x, __gcd(y, z)); x /= nwdd; y /= nwdd; z /= nwdd; zm.pb({1, x, y, z}); vec.pb({{x, y}, z}); T[ktor] = {{x, y}, z}; ktor++; } else { int nr; cin >> nr; nr--; zm.pb({2, nr, nr, nr}); } } przesort(); // cout << "XD" << endl; ktor = 0; rep(i, q) { upd now = zm[i]; bool c1, c2, c3; // cout << "i = " << i << endl; if (now.typ == 1) { c2 = dod(przemien(T[ktor])); // cout << "REL" << endl; c1 = spr1(); // cout << "FR" << endl; c3 = patrz(T[ktor], ktor); // cout << "SK" << endl; ktor++; } else { c2 = odejm(przemien(T[zm[i].x])); c1 = spr1(); // cout << "FR" << endl; c3 = patrz2(T[zm[i].x], zm[i].x); // cout << "SK" << endl; } // cout << "ZIIUUUUUUUUUUUUUUUUUUUUUUUUUUUUMMM lic = " << lic << '\n'; if (c1) { cout << 1 << '\n'; } else if (c2) { cout << 2 << '\n'; } else if (c3) { cout << 3 << '\n'; } else { cout << 0 << '\n'; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...