Submission #986338

#	Time	Username	Problem	Language	Result	Execution time	Memory
986338		cadmiumsky	Mixture (BOI20_mixture)	C++17	100 / 100	375 ms	22644 KiB

Mixture

#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

//#ifndef DLOCAL
//   #define cin fin
//   #define cout fout
//   ifstream cin(".in");
//   ofstream cout(".out");
//#endif

using ll = long long;
using ld = long double;

//#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;

using point = pair<double,double>;
#define x first
#define y second

#define ERROR (-100)

const double PI = acos(-1);
const double eps = 1e-10;

double difference_(double start, double finish) {
   start -= eps;
   finish += eps;
   
   if(start < finish) return finish - start;
   return finish - start + 2 * PI;
}
static inline double reeps(double X) {
   return X;
}
double angle(double A, double B) {
   auto U = atan2(A, B);
   if(U < 0) return reeps(2. * PI + U);
   return reeps(U);
}

double flip(double angle) {
   if(angle == ERROR) return ERROR;
   return angle < PI? angle + PI : angle - PI;
}


template<typename T>
struct MP {
   map<double, T> freq;
   T& operator[](double a) {
      auto it = freq.lower_bound(a - eps);
      if(it != freq.end() && it -> first <= a + eps) return freq[it -> first];
      return freq[a];
   }
};

struct AdjacentDifferences {
   multiset<double> angles;
   multiset<double>::iterator before(multiset<double>::iterator it) {
      if(it == angles.begin()) return prev(angles.end());
      return prev(it);
   }
   multiset<double>::iterator after(multiset<double>::iterator it) {
      if(next(it) == angles.end()) return angles.begin();
      return next(it);
   }
   
   double difference(multiset<double>::iterator L, multiset<double>::iterator R) {
      //cerr << difference_(*L, *R) << '\n';
      if(R == angles.begin() && abs(*L - *R) <= eps) return 2 * PI;
      return difference_(*L, *R);
   }
   
   multiset<double> differences;
   
   pair<double, double> jump = pair<double, double>{ERROR, ERROR};
   
   void insert(double U) {      
      auto it = angles.insert(U), L = before(it), R = after(it);
      if(angles.size() >= 3) {
         if(difference(L, R) > PI) jump = make_pair(ERROR, ERROR);
      }
      if(angles.size() >= 2) {
         if(difference(L, it) > PI) jump = make_pair(*L, *it);
         if(difference(it, R) > PI) jump = make_pair(*it, *R);
      }
   }
   
   void erase(double U) {
      auto it = angles.find(U), L = before(it), R = after(it);
      if(angles.size() >= 2) {
         if(difference(L, it) > PI) jump = make_pair(ERROR, ERROR);
         if(difference(it, R) > PI) jump = make_pair(ERROR, ERROR);
      }
      angles.erase(it);
      if(angles.size() >= 2) {
         if(difference(L, R) > PI) jump = make_pair(*L, *R);
      }
      
   }
   
   bool count(double L, double R) {
      if(L == ERROR || R == ERROR) return 0;
      if(L > R) return count(L, 2 * PI) || count(0, R);
      auto it = angles.lower_bound(L - eps);
      if(it != angles.end() && *it <= R + eps) return 1;
      return 0;
   }
};

namespace DS {
   int cnt_0;
   
   MP<pii> freq;
   MP<int> point_freq, vector_freq;
   
   AdjacentDifferences point_adjdif, vector_adjdif;
   
   int paired_with_vector = 0;
   int ok_pairs = 0;
   
   void insert(point a) {
      if(a.x == 0 && a.y == 0) cnt_0++;
      else {
         double U = angle(a.y, a.x);
         //cerr << "\t + point " << U << '\n';
         point_adjdif.insert(U);
         
         double link = (U < PI? U : U - PI);
         bool ready = 0;
         
         if(freq[link].first * freq[link].second == 0) ready = 1;
         if(U < PI) freq[U].first++;
         else freq[U - PI].second++;
         if(freq[link].first * freq[link].second != 0 && ready) ok_pairs++;
         
         paired_with_vector += vector_freq[flip(U)];
         point_freq[U]++;
      }
   }
   
   void erase(point a) {
      if(a.x == 0 && a.y == 0) cnt_0--;
      else {
         double U = angle(a.y, a.x);
         point_adjdif.erase(U);
         
         double link = (U < PI? U : U - PI);
         bool ready = 0;
         
         if(freq[link].first * freq[link].second != 0) ready = 1;
         if(U < PI) freq[U].first--;
         else  freq[U - PI].second--;
         if(freq[link].first * freq[link].second == 0 && ready) ok_pairs--;
         
         paired_with_vector -= vector_freq[flip(U)];
         point_freq[U]--;
      }
   }
   
   void insert_vector(point a) {
      double U = angle(a.y, a.x);
      //cerr << "\t + vector " << U << '\n';
      vector_adjdif.insert(U);
      paired_with_vector += point_freq[flip(U)];
      vector_freq[U]++;
      return;
   }
   
   void erase_vector(point a) {
      double U = angle(a.y, a.x);
      vector_adjdif.erase(U);
      paired_with_vector -= point_freq[flip(U)];
      vector_freq[U]--;
      return;
   }
      
   
   int query() {
      //cerr << '\t' << angles.size() << '\n';
      
      
      if(cnt_0) return 1;
      if(ok_pairs) return 2;
      if(paired_with_vector) return 2;
      auto [l, r] = point_adjdif.jump;
      //cerr << l << ' ' << r << '\t';
      //for(auto x : point_adjdif.angles) cerr << x << ' ';
      //cerr << '\n';
      
      if(point_adjdif.jump.first == ERROR && sz(point_adjdif.angles) >= 3) return 3;
      if(vector_adjdif.jump.second == ERROR  && sz(vector_adjdif.angles) >= 3) return 3;
      
      //auto [l, r] = point_adjdif.jump;
      //cerr << l << ' ' << r << '\n';
      l = flip(l);
      r = flip(r);
      swap(l, r);
      if(vector_adjdif.count(l, r)) return 3;
      //cerr << l << ' ' << r << '\n';
      
      tie(l, r) = vector_adjdif.jump;
      l = flip(l);
      r = flip(r);
      swap(l, r);
      if(point_adjdif.count(l, r)) return 3;
      return 0;
   }
   
   
   
}

signed main() {
   cin.tie(0) -> sync_with_stdio(0);
   double a, b, c;
   
   int este_zero = 0;
   
   cin >> a >> b >> c;
   point center;
   
   double T[3] = {a, b, c};
   
   vector<int> idx(3);
   iota(all(idx), 0);
   #ifndef DLOCAL
      sort(all(idx), [&](int a, int b) { return T[a] > T[b]; });
   #endif
   a = T[idx[0]];
   b = T[idx[1]];
   c = T[idx[2]];
   
   //cerr << a << ' ' << b << ' ' << c << '\n';
   
   center.x = b / a;
   center.y = c / a;
   
   int n;
   cin >> n;
   vector<tuple<double, double, double>> v;
   
   //if(este_zero == 0) {
      vector<int> pula;
      for(int i = 0; i < n; i++) {
         char ch;
         cin >> ch;
         point here;
         bool ebine = 1;
         
         if(ch == 'R') {
            int t;
            cin >> t;
            t--;
            tie(a, b, c) = v[t];
         }
         else {
            cin >> a >> b >> c;
            T[0] = a, T[1] = b, T[2] = c;
            a = T[idx[0]];
            b = T[idx[1]];
            c = T[idx[2]];
            
            v.emplace_back(a, b, c);
         }
            
         if(a == 0) here.x = b, here.y = c;
         else {
            here.x = b / a - center.x;
            here.y = c / a - center.y;
         }
         
         
         if(ch == 'R') {
            if(a != 0)
               DS::erase(here);
            else
               DS::erase_vector(here);
         }
         else {
            if(a != 0)
               DS::insert(here);
            else
               DS::insert_vector(here);
         }
         
         cout << DS::query() << '\n';
      }
   
}

/**
      Istenem! Nu poate fi real.
-- Surse verificate
*/

Compilation message (stderr)

Mixture.cpp: In function 'int main()':
Mixture.cpp:254:15: warning: unused variable 'ebine' [-Wunused-variable]
  254 |          bool ebine = 1;
      |               ^~~~~
Mixture.cpp:223:8: warning: unused variable 'este_zero' [-Wunused-variable]
  223 |    int este_zero = 0;
      |        ^~~~~~~~~

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