제출 #1263169

#제출 시각아이디문제언어결과실행 시간메모리
1263169M_W_13Mixture (BOI20_mixture)C++20
30 / 100
5 ms1092 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[6]; 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}; } int zmiana(pair<ll, ll> p) { if (p.nd == 0) { if (p.st < 0) { return 2; } return 5; } if (p.nd < 0) { if (p.st < 0) { return 1; } return 0; } if (p.st > 0) { return 4; } return 3; } void wyp(__int128_t x) { vector<char> vec; // if (x == 0) { // cout << "BRRRRUUUUUUUUUUUUUUUUUHHHHHHHHH" << '\n'; // return ; // } while (x > 0) { int t = (x % 10); char c = t + '0'; vec.pb(c); x /= 10; } reverse(vec.begin(), vec.end()); for (auto c: vec) { cout << c; } cout << '\n'; } bool por(pair<pair<ll, ll>, int> x2, pair<pair<ll, ll>, int> y2) { pair<ll, ll> x = x2.st; pair<ll, ll> y = y2.st; if (x2 == y2) return false; if (zmiana(x) == zmiana(y)) { // cout << "TUuuuuuuuuu = " << x.st << " " << x.nd << " " << y.st << " " << y.nd << '\n'; bool zmien = true; if (x.st < 0 && x.nd > 0) { zmien = false; } else if (x.st > 0 && x.nd < 0) { zmien = false; } __int128_t a = abs(x.st); __int128_t b = abs(x.nd); __int128_t c = abs(y.st); __int128_t d = abs(y.nd); __int128_t w1 = a * d; __int128_t w2 = b * c; // wyp(w1); // wyp(w2); if (zmien) { return (w1 > w2); } return (w1 < w2); } return zmiana(x) > zmiana(y); } void przesort() { int sz = vec.size(); // cout << "szzzzzzzzzzzzzzzzz = " << sz << '\n'; rep(i, sz) { pom[zmiana(przemien(vec[i]))].pb({przemien(vec[i]), i}); } for (int c2 = 5; c2 >= 0; c2--) { sort(pom[c2].begin(), pom[c2].end(), por); } int kt = 1; // cout << "SORT" << '\n'; for (int c2 = 5; c2 >= 0; c2--) { for (auto p: pom[c2]) { jaki[p.nd] = kt; // cout << "kt = " << kt << " "; // pair<ll, ll> paraa = przemien(T[p.nd]); // wypisz(paraa); // cout << '\n'; // ld a = paraa.st; // ld b = paraa.nd; // ld c = a/b; // cout << zmiana(paraa) << '\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...