제출 #1129252

#제출 시각아이디문제언어결과실행 시간메모리
1129252mircea_007Mixture (BOI20_mixture)C++20
0 / 100
0 ms328 KiB
#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 { int 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' } }; /*#include <math.h> using ftype = double; const ftype PI = 4 * atan(1); bool is_big_inprecis( const Point &a, const Point &b ) { ftype alfa = atan2( a.y.a / (ftype)a.y.b, a.x.a / (ftype)a.x.b ); ftype beta = atan2( b.y.a / (ftype)b.y.b, b.x.a / (ftype)b.x.b ); ftype delta = beta - alfa; if( delta < 0 ) delta += 2 * PI; if( delta >= 2 * PI ) delta -= 2 * PI; return delta > PI; }*/ bool is_big( const Point& a, const Point& b ) { bool ret; if( a.cadran() < 2 ) ret = (b < a || (-a) < b); else ret = (b < a && (-a) < b); // bool good_ret = is_big_inprecis( a, b ); // if( ret != good_ret ){ // printf( "is_big( (%lld/%lld, %lld/%lld) -> (%lld/%lld, %lld/%lld) ) da %d in loc de %d\n", a.x.a, a.x.b, a.y.a, a.y.b, b.x.a, b.x.b, b.y.a, b.y.b, int(ret), int(good_ret) ); // printf( "cadran a = %d\n", a.cadran() ); // } 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; OriginMixture(): origin_freq(0), angles(), plusminus(0), big_angles(0), insertions() {} int min_mixture() { if( origin_freq ) return 1; if( plusminus ) return 2; if( (int)angles.size() >= 2 && !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; }

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

Mixture.cpp: In function 'Point read_point()':
Mixture.cpp:101:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |   scanf( "%d%d%d", &S, &P, &G );
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Mixture.cpp: In function 'int main()':
Mixture.cpp:217:13: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  217 |   for( scanf( "%d", &ops ); ops--; ){
      |        ~~~~~^~~~~~~~~~~~~~
Mixture.cpp:224:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  224 |       scanf( "%d", &idx );
      |       ~~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...