Submission #1151202

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151202		pudelos	Mixture (BOI20_mixture)	C++20	13 / 100	2091 ms	456 KiB

Mixture

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i, a, b) for(int i=a; i<=b; ++i)
#define sz(A) (int)(A.size())
#define eb emplace_back
#define pb push_back
#define pi pair<int, int>
#define f x
#define s y
#define rs resize
#define V vector


struct Ulamek {
  int a, b;

  Ulamek (int licznik, int mianownik) : a(licznik), b(mianownik) {
    // int nwd = __gcd(a, b);
    // a/=nwd;
    // b/=nwd;
  };
  
  Ulamek operator + (const Ulamek &u) const {
    int licznik = a*u.b + u.a*b;
    int mianownik = u.b*b;
    int nwd = __gcd(licznik, mianownik);
    return Ulamek(licznik/nwd, mianownik/nwd);
  }

  Ulamek operator - (const Ulamek &u) const {
    int licznik = a*u.b - u.a*b;
    int mianownik = u.b*b;
    // int nwd = __gcd(licznik, mianownik);
    // return Ulamek(licznik/nwd, mianownik/nwd);
    return Ulamek(licznik, mianownik);
  }

  Ulamek operator * (const Ulamek &u) const {
    int licznik = u.a*a;
    int mianownik = u.b*b;
    int nwd = __gcd(licznik, mianownik);
    return Ulamek(licznik/nwd, mianownik/nwd);
  }

  bool operator == (const Ulamek &u) const {
    return (a*u.b == b*u.a);
  }

  bool operator < (const Ulamek &u) const {
    return a*u.b < b*u.a;
  }

  bool operator > (const Ulamek &u) const {
    return !(a*u.b < b*u.a || (a*u.b == b*u.a));
  }
};

struct Punkt {
  Ulamek x, y;
  Punkt (Ulamek a, Ulamek b): x(a), y(b) {}
  bool operator<(const Punkt& p) const {
    if (x < p.x) return true;
    if (x > p.x) return false;
    return y < p.y;
  }
};


V<Punkt> D;
V<bool> del;
multiset<Punkt> punkty;
int n;



Ulamek ccw(Punkt a, Punkt b, Punkt c) {
  a.f=a.f-c.f;
  b.f=b.f-c.f;
  a.s=a.s-c.s;
  b.s=b.s-c.s;
  return (a.f*b.s-b.f*a.s);
}

Ulamek licz_p(int i, int j, int k) {
  Punkt a = D[i];
  Punkt b = D[j];
  Punkt c = D[k];
  Ulamek P = (a.f*(b.s-c.s) + b.f*(c.s-a.s) + c.f*(a.s-b.s));
  if(P.a*P.b<0) {
    if(P.a<0) P.a=-P.a;
    else P.b=-P.b;
  }
  return P;
}

int check() {
  if(punkty.find(D[0])!=punkty.end()) return 1;
  FOR(i, 1, sz(D)-1) FOR(j, 1, sz(D)-1) {
    if(i==j) continue;
    if(del[i] || del[j]) continue;
    if ((min(D[i].f, D[j].f) < D[0].f && D[0].f < max(D[i].f, D[j].f)) ||
        (D[i].f == D[j].f && D[i].f == D[0].f &&
        min(D[i].s, D[j].s) < D[0].s && D[0].s < max(D[i].s, D[j].s))) {
      if (ccw(D[i], D[j], D[0]).a == 0) return 2;
    }

  }

  FOR(i, 1, sz(D)-1) FOR(j, i+1, sz(D)-1) FOR(k, j+1, sz(D)-1) {
    // if((i==j || i==k) || j==k) continue;
    if(del[i] || (del[j] || del[k])) continue;
    Ulamek pole = licz_p(i, j, k);
    if(pole.a==0) continue;
    Ulamek P1 = licz_p(i, j, 0);
    Ulamek P2 = licz_p(0, k, i);
    Ulamek P3 = licz_p(j, 0, k);
    if(pole==P1+P2+P3) {
      // cout << i << ' ' << j << ' ' << k << '\n';
      // cout << D[i].f.a << ' ' << D[i].f.b << ' ' << D[i].s.a << ' ' << D[i].s.b << '\n';
      // cout << D[j].f.a << ' ' << D[j].f.b << ' ' << D[j].s.a << ' ' << D[j].s.b << '\n';
      // cout << D[k].f.a << ' ' << D[k].f.b << ' ' << D[k].s.a << ' ' << D[k].s.b << '\n';
      // // cout << D[i].s << ' ' << D[j].f << ' ' << D[j].s << ' ' << D[k].f << ' ' << D[k].s << '\n';
      //     cout << P1.a << ' ' << P1.b << ' ' << '\n';
      //     cout << P2.a << ' ' << P2.b << ' ' << '\n';
      //     cout << P3.a << ' ' << P3.b << ' ' << '\n';
      //     cout << "pole: " << pole.a << ' ' << pole.b << ' ' << '\n';
      return 3;
    }
  }

  return 0;
}

int A, B, C;

signed main() {
  cin.tie(0) -> ios_base::sync_with_stdio(0);
  cin >> A >> B >> C;
  D.pb(Punkt(Ulamek(A, (A+B+C)), Ulamek(B, (A+B+C))));
  cin >> n;
  del.rs(n+1);

  // int cnt=0;
  char typ;
  int a, b, c;
  FOR(i, 1, n) {
    cin >> typ;
    if(typ=='A') {
      cin >> a >> b >> c;
      D.pb(Punkt(Ulamek(a, (a+b+c)), Ulamek(b, (a+b+c))));
      punkty.insert(Punkt(Ulamek(a, (a+b+c)), Ulamek(b, (a+b+c))));
    } else {
      int idx;
      cin >> idx;
      del[idx]=1;
      punkty.erase(punkty.find(D[idx]));
    }
    int odp = check();
    cout << odp << '\n';
  }
}

• Subtask 1: 13 / 13
• Subtask 2: 0 / 17
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40