Submission #986248

#	Time	Username	Problem	Language	Result	Execution time	Memory
986248		vjudge1	Mixture (BOI20_mixture)	C++17	0 / 100	1 ms	600 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

const double PI = acos(-1);

double difference(double start, double finish) {
   if(start > finish) return start - finish;
   return start - finish + 2 * PI;
}
double angle(double A, double B) {
   auto U = atan2(A, B);
   if(U < 0) return 2. * PI + U;
   return U;
}

namespace DS {
   int cnt_0;
   
   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);
   }
   
   multiset<double> differences;
   
   map<double, pii> freq;
   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);
         auto it = angles.insert(U), L = before(it), R = after(it);
         if(angles.size() >= 3)
            differences.erase(differences.find(difference(*L, *R)));
         if(angles.size() >= 2) {
            differences.insert(difference(*L, *it));
            differences.insert(difference(*it, *R));
         }
         
         
         double link = (U < PI? U : U - PI);
         //cerr << setprecision(8) << fixed << U / PI * 180. << ' ' << link / PI * 180. << '\n';
         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++;
      }
   }
   
   
   void erase(point a) {
      if(a.x == 0 && a.y == 0) cnt_0--;
      else {
         double U = angle(a.y, a.x);
         auto it = angles.find(U), L = before(it), R = after(it);
         //cerr << "heh\n";
         if(angles.size() >= 2) {
            //for(auto x : differences) cerr << x / PI * 180. << ' ';
            //cerr << '\n';
            
            //cerr << *L << ' ' << *it << ' ' << *R << '\n';
            
            differences.erase(differences.find(difference(*L, *it)));
            differences.erase(differences.find(difference(*it, *R)));
         }
         if(angles.size() >= 3)
            differences.insert(difference(*L, *R));
         //cerr << "heh\n";
         
         angles.erase(it);
         
         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--;
      }
   }
   
   int query() {
      //cerr << '\t' << angles.size() << '\n';
      if(cnt_0) return 1;
      if(ok_pairs) return 2;
      if(sz(angles) <= 1 || *differences.rbegin() > PI) return 0;
      return 3;
   }
   
   
   
}

signed main() {
   cin.tie(0) -> sync_with_stdio(0);
   double a, b, c;
   cin >> a >> b >> c;
   
   point center(b / a, c / a);
   
   int n;
   cin >> n;
   vector<point> v;
   for(int i = 0; i < n; i++) {
      char ch;
      cin >> ch;
      point here;
      
      if(ch == 'R') {
         int t;
         cin >> t;
         t--;
         here = v[t];
      }
      else {
         cin >> a >> b >> c;
         here.x = b / a - center.x;
         here.y = c / a - center.y;
         v.emplace_back(here);
      }
      
      if(ch == 'R')
         DS::erase(here);
      else
         DS::insert(here);
      cout << DS::query() << '\n';
      cout.flush();
   }
   
   
}

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

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