Submission #1129444

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129444		mircea_007	Mixture (BOI20_mixture)	C++20	100 / 100	131 ms	9100 KiB

Mixture

#include <stdio.h>
#include <ctype.h>

int nextc() {
  int ch;
  while( isspace( ch = fgetc( stdin ) ) );
  return ch;
}

#include <algorithm>
#include <vector>
#include <set>

using ll = long long;
struct Rat {
  // conditie extra: b este mereu pozitiv
  ll a, b;
  Rat( ll a = 0, ll b = 1 ): a(a), b(b) {}
  Rat operator - () const { return Rat(-a, b); }

  Rat operator + ( const Rat& that ) const { return Rat(a * that.b + b * that.a, b * that.b); }
  Rat operator - ( const Rat& that ) const { return *this + (-that); }

  Rat operator += ( const Rat& that ) { return *this = *this + that; }
  Rat operator -= ( const Rat& that ) { return *this = *this - that; }

  bool operator == ( const Rat& that ) const { return a * (__int128)that.b == that.a * (__int128)b; }
};

struct Point {
  // conditie extra: x.b == y.b mereu
  Rat x, y;
  Point( Rat x, Rat y ): x(x), y(y) {}
  Point( int S, int P, int G ): x(S, S + P + G), y(P, S + P + G) {}
  Point operator - () const { return Point(-x, -y); }

  Point operator + ( const Point& that ) const { return Point(x + that.x, y + that.y); }
  Point operator - ( const Point& that ) const { return Point(x - that.x, y - that.y); }

  Point operator += ( const Point& that ) { return *this = *this + that; }
  Point operator -= ( const Point& that ) { return *this = *this - that; }

  bool operator == ( const Point& that ) const { return x == that.x && y == that.y; }

  // 1 0
  // 2 3
  int cadran() const {
    ll X = x.a, Y = y.a;
    if( X >= 0 && Y > 0 ) return 0;
    if( X < 0 && Y >= 0 ) return 1;
    if( X <= 0 && Y < 0 ) return 2;
    if( X > 0 && Y <= 0 ) return 3;
    // originea
    return -1;
  }

  // sortare trigonometrica
  bool operator < ( const Point& that ) const {
    int cthis = cadran(), cthat = that.cadran();
    if( cthis != cthat )
      return cthis < cthat;

    return that.y.a * (__int128)x.a > y.a * (__int128)that.x.a; // 'determinant cu originea'
  }
};

bool is_big( const Point& a, const Point& b ) {
  bool ret;

  if( !(a < b) && !(b < a) )
    return true; // luam 2pi ca si varianta proasta
  
  if( a.cadran() < 2 )
    ret = (b < a || (-a) < b);
  else
    ret = (b < a && (-a) < b);

  return ret;
}

Point read_point() {
  int S, P, G;
  scanf( "%d%d%d", &S, &P, &G );
  return Point(S, P, G);
}

struct OriginMixture {
  int origin_freq;

  std::multiset<Point> angles;
  int plusminus; // cate perechi unghiuri opuse avem?
  int big_angles; // diferente > PI

  std::vector<Point> insertions;

  // big_angles = 1 pentru ca cu un eleme avem 2PI
  OriginMixture(): origin_freq(0), angles(), plusminus(0), big_angles(1), insertions() {}
  int min_mixture() {
    if( origin_freq )
      return 1;
    if( plusminus )
      return 2;
    if( !big_angles )
      return 3;

    return 0;
  }

  void insert( Point P ) {
    insertions.push_back( P );

    // inseram originea?
    if( P == Point(Rat(0), Rat(0)) ){
      origin_freq++;
      return;
    }

    // primul inserat?
    if( (int)angles.size() == 0 ){
      angles.insert( P );
      return;
    }

    // inseram panta
    bool plus = (angles.find( P ) != angles.end());
    bool minus = (angles.find( -P ) != angles.end());

    if( !plus && minus )
      plusminus++;

    if( plus ){
      angles.insert( P );
      return;
    }

    auto prev_it = angles.lower_bound( P );
    if( prev_it == angles.begin() )
      prev_it = angles.end();
    prev_it--;

    auto next_it = angles.upper_bound( P );
    if( next_it == angles.end() )
      next_it = angles.begin();

    big_angles -= is_big( *prev_it, *next_it );
    big_angles += is_big( *prev_it, P );
    big_angles += is_big( P, *next_it );

    angles.insert( P );
  }

  void erase( int idx ) {
    Point P = insertions[idx];

    // scoatem originea?
    if( P == Point(Rat(0), Rat(0)) ){
      origin_freq--;
      return;
    }

    // ultimum scos?
    if( (int)angles.size() == 1 ){
      angles.erase( angles.find( P ) );
      return;
    }

    // scoatem panta
    angles.erase( angles.find( P ) ); // activitati obisnuite multiset

    bool plus = (angles.find( P ) != angles.end());
    bool minus = (angles.find( -P ) != angles.end());

    if( !plus && minus )
      plusminus--;

    if( plus )
      return;

    auto prev_it = angles.lower_bound( P );
    if( prev_it == angles.begin() )
      prev_it = angles.end();
    prev_it--;

    auto next_it = angles.upper_bound( P );
    if( next_it == angles.end() )
      next_it = angles.begin();

    big_angles -= is_big( *prev_it, P );
    big_angles -= is_big( P, *next_it );
    big_angles += is_big( *prev_it, *next_it );
  }
};

int main() {
  Point origin = read_point();
  OriginMixture mix;

  int ops;
  for( scanf( "%d", &ops ); ops--; ){
    char task = nextc();

    if( task == 'A' )
      mix.insert( read_point() - origin );
    else{ // if( task == 'R' )
      int idx;
      scanf( "%d", &idx );
      mix.erase( idx - 1 );
    }

    printf( "%d\n", mix.min_mixture() );
  }
  
  return 0;
}

Compilation message (stderr)

Mixture.cpp: In function 'Point read_point()':
Mixture.cpp:83:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |   scanf( "%d%d%d", &S, &P, &G );
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Mixture.cpp: In function 'int main()':
Mixture.cpp:199:13: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  199 |   for( scanf( "%d", &ops ); ops--; ){
      |        ~~~~~^~~~~~~~~~~~~~
Mixture.cpp:206:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  206 |       scanf( "%d", &idx );
      |       ~~~~~^~~~~~~~~~~~~~

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