제출 #986259

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
986259		vjudge1	Mixture (BOI20_mixture)	C++17	0 / 100	0 ms	348 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 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);
}

const double eps = 1e-9;

struct MP {
   map<double, pii> freq;
   pii& 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];
   }
};

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;
   MP 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;
         //cerr << ok_pairs << '\t';
         
         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;
   
   int este_zero = 0;
   
   cin >> a >> b >> c;
   point center;
   
   double T[3] = {a, b, c};
   
   vector<int> idx(3);
   iota(all(idx), 0);
   sort(all(idx), [&](int a, int b) { return T[a] > T[b]; });
   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<point> 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--;
            here = v[t];
            ebine = pula[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]];
            
            if(a == 0) pula.emplace_back(0), ebine = 0;
            else {
               pula.emplace_back(1);
               here.x = b / a - center.x;
               here.y = c / a - center.y;
               v.emplace_back(here);
            }
         }
         
         
         if(ebine) {
            if(ch == 'R')
               DS::erase(here);
            else
               DS::insert(here);
         }
         cout << DS::query() << '\n';
      }
   //}
   //if(este_zero == 1) {
      //int cnt[4] = {0, 0, 0, 0};
      //vector<int> val;
      //for(int i = 0; i < n; i++) {
         //char ch;
         //cin >> ch;
         //int poz;
         //if(ch == 'R') {
            //int t;
            //cin >> t;
            //t--;
            //poz = val[t];
         //}
         //else {
            //cin >> a >> b >> c;
            //if(a != 0) poz = 3;
            //if()
         //}
      //}
   //}
   
}

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

컴파일 시 표준 에러 (stderr) 메시지

Mixture.cpp: In function 'int main()':
Mixture.cpp:147:8: warning: unused variable 'este_zero' [-Wunused-variable]
  147 |    int este_zero = 0;
      |        ^~~~~~~~~

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