Submission #349561

#	Time	Username	Problem	Language	Result	Execution time	Memory
349561		CaroLinda	Printed Circuit Board (CEOI12_circuit)	C++14	90 / 100	248 ms	28528 KiB

circuit

#include <bits/stdc++.h>
 
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops") 
#define sz(x) (int)(x.size())
#define debug printf
#define lp(i,a,b) for(int i = a ; i < b; i++)
#define pb push_back
#define ff first
#define ss second
#define mk make_pair
#define pii pair<int,int>
#define ll long long 
#define all(x) x.begin(),x.end()
 
const int MAX = 2e5+10 ;
 
using namespace std ;
 
char c ;
void readInt(int &num)
{
	num = 0 ;
	for(c = getchar() ; (c > 47 && c <58 ) ; c = getchar() )
		num = num*10 + c - 48 ;
}
 
void readLong(ll &num ) 
{
	num = 0 ;
	for(c = getchar() ; (c> 47 && c < 58 ) ; c = getchar() )
		num = num*10 + c - 48 ;
}
 
int N ;
int myId[MAX] ;
ll num[MAX], den[MAX] ;
 
struct Point
{
 
    ll x , y ;
 
    Point(ll x=0, ll y=0):x(x), y(y) {}
    
    bool operator == ( Point other ) const { return x == other.x && y == other.y ; }
    bool operator != (Point other ) const { return x != other.x || y != other.y ; }
    Point operator - (Point other) const { return Point(x-other.x, y-other.y) ; } 
    ll operator % (Point other) const { return x*other.y - y*other.x ; }
    ll operator *(Point other) const { return x*other.x + y*other.y ; }
    void read() { scanf("%lld %lld", &x, &y) ; }
} ;
 
struct Line
{
	Point p1, p2 ; 
	Line( Point p1 = Point(0,0) , Point p2 = Point(0,0) ) : p1(p1) , p2(p2) {} 
}  ;
 
bool isLess(ll num1, ll den1, ll num2, ll den2 )
{
	//It doesn't happen that den < 0, because x is always positive 
 
   if(num1 <= 1000000000 && den1 <= 1000000000 && num2 <= 1000000000 && den2 <= 1000000000 )
   	return num1*den2 < num2*den1 ;
 
	ll q1 = num1/den1 ;
	ll q2 = num2/den2 ;
	ll r1 = num1%den1 ;
	ll r2 = num2%den2 ;
 
	if( q1 != q2 ) return q1 < q2 ;
	if( r1 == 0 || r2 == 0 ) return r1 == 0 && r2 > 0 ;
 
	return isLess(den2, r2, den1, r1 ) ;
}
 
ll getNum( Line t, int id )
{
	return den[id] * ( t.p1.y*t.p2.x - t.p1.x*t.p2.y ) ;
}
 
ll getDen(Line t, int id )
{
	return den[id] * ( t.p1.y - t.p2.y ) - num[id] * (t.p1.x-t.p2.x ) ;
}
 
struct Seg
{

	Line tree[MAX*2] ;
	int l[MAX*2], r[MAX*2] ;

	void ini()
	{
		for(int i= N ; i < 2*N ; i++ ) l[i] = r[i] = i - N ;

		for(int i= N-1 ; i > 0 ; i-- )
		{
			l[i] = min(l[i<<1], l[i<<1|1] ) ;
			r[i] = max(r[i<<1], r[i<<1|1] ) ;
		}

	}

	void upd(int pos, Line t )
	{
		if( tree[pos].p1 == Point(0,0) ) return (void)(tree[pos] = t ) ; 
			 
		for(auto e : {l[pos] , r[pos] } ) 
		{
			ll num1 = getNum(tree[pos], e) ;
			ll den1 = getDen(tree[pos], e ) ;
			ll num2 = getNum(t, e ) ;
			ll den2 = getDen(t, e ) ;
				
			if(den1 < 0 ) num1 = -num1 , den1 = -den1 ;
			if( den2 < 0 ) num2 = -num2, den2 = -den2 ;
 
			if( tree[pos].p1.x == tree[pos].p2.x ) num1 = tree[pos].p1.x, den1 = 1LL ;
			if(t.p1.x == t.p2.x ) num2 = t.p1.x , den2 = 1LL ;
 
			if(isLess(num1, den1, num2, den2 ) ) return ;
 
		}
		tree[pos] = t ;

	}

	void addLine(int l, int r, Line t )
	{
		for( l += N , r += N ; l < r ; l >>= 1 , r >>= 1 )
		{
			if(l&1) 
			{
				upd(l, t) ;
				l++ ;
			}
			if(r&1) upd(--r,t) ;
		}			
	}

	bool qry(int pos, Point p )
	{
		for(pos += N ; pos > 0 ; pos >>= 1 )
		{
			if( tree[pos].p1 == Point(0,0) || tree[pos].p1 == p || tree[pos].p2 == p ) continue ;	

			ll val1 = (tree[pos].p2 - tree[pos].p1)%(p-tree[pos].p1) ;
			ll val2 = (tree[pos].p2-tree[pos].p1)%(Point(0,0)-tree[pos].p1 ) ;
 
			if( (val1 < 0 ) != (val2 < 0)  ) return false ;
			
		}

		return true ;
	}

	void print()
	{
		for(int i = 1 ; i < 2*N ; i++ )
		{
			printf("[%d,%d] -> %lld %lld and %lld %lld\n", l[i], r[i] , tree[i].p1.x, tree[i].p1.y, tree[i].p2.x, tree[i].p2.y ) ;
		}
	}

} seg ;
 
int main()
{
 
	readInt(N) ;
		 
	vector<Point> p(N) ;
	vector< pair<Point, int> > sorted ;
 
	for(int i = 0 ; i < N ; i++ ) 
	{
		readLong(p[i].x ) ;
		readLong(p[i].y ) ;
		sorted.push_back( make_pair(p[i], i ) ) ;
	}
 
 	sort(all(sorted), [&]( pair<Point,int> a, pair<Point,int> b ) 
	{
		if( a.first%b.first == 0 ) return (b.first-a.first)*(Point(0,0)-a.first ) < 0 ;
		return a.first%b.first > 0 ;	
	} ) ; 
 
	int j = -1 ;
	for(int i = 0 ; i < N ; i++ ) 
	{
	   if(!i || sorted[i-1].first%sorted[i].first != 0 ) j++ ;
	   		
		myId[ sorted[i].second ] = j ;
 
		num[j] = sorted[i].first.y ;
		den[j] = sorted[i].first.x ;
	}
 
	seg.ini() ;		

	for(int i = 0 , nxt = 1 ; i < N ; i++, nxt++ )
	{
		if(nxt ==  N ) nxt = 0 ;
 
		int l = myId[i] , r = myId[nxt] ;
 
      if(l == r ) continue ;
		if( l > r ) swap(l,r) ;
 
		seg.addLine(l,r+1, Line( p[i], p[nxt] ) ) ;  

	} 
 
 
	//Don't forget to check if there is someone in the same polar angle that mine (because, if there is, it fucks everything up )
 
	vector<int> ans ;
	for(int i=0 ; i < N ; i++ )
	{
		if(i && sorted[i-1].first%sorted[i].first == 0 ) continue ;
		if(seg.qry(myId[ sorted[i].second ] , sorted[i].first ) ) ans.push_back(sorted[i].second ) ;
	}
 
	sort(all(ans) ) ;
 
	printf("%d\n", sz(ans ) ) ;
	for(auto e : ans ) printf("%d ", e+1 ) ;
	printf("\n") ;
 
 
}

Compilation message (stderr)

circuit.cpp:4: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("O3")
      | 
circuit.cpp:5: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("unroll-loops")
      |

• Subtask 1: 90 / 100