Submission #1068492

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068492		lollipop	Naval battle (CEOI24_battle)	C++17	76 / 100	263 ms	32772 KiB

Main

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
//#define int long long
#define pb push_back
#define s second
#define f first
#define pf push_front
#define inf 100000000000000000
#define bitebi __builtin_popcountll
#define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
#define YES cout <<"YES\n"
#define NO cout << "NO\n"
#define debug cout << "Here Fine" << endl ;
#define pr pair < int , int >
#define fbo find_by_order // returns iterator
#define ook order_of_key // returns strictly less numbers than key
using namespace std ;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
using namespace __gnu_pbds;
using namespace __gnu_cxx;
template<class T> using ordered_set =tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update> ;
const double Pi=acos(-1.0);
const double EPS=1E-8;
const int mod =  1000000007 ;
const int mod1 = 998244353 ;
const int N = 2e5 + 10 ;
mt19937 R(time(0));
map < int , int > ma , ma1 ;
 
 
 
struct Point {
    int x;
    int y;
};
Point val[ N ] ;
 
 
bool willIntersect(Point p1, char d1, Point p2, char d2, int &time) {
    // Calculate deltas for movement
    int dx1 = (d1 == 'E') ? 1 : (d1 == 'W') ? -1 : 0;
    int dy1 = (d1 == 'N') ? -1 : (d1 == 'S') ? 1 : 0;
    int dx2 = (d2 == 'E') ? 1 : (d2 == 'W') ? -1 : 0;
    int dy2 = (d2 == 'N') ? -1 : (d2 == 'S') ? 1 : 0;
 
    // Relative movement per time step
    int rel_dx = dx2 - dx1;
    int rel_dy = dy2 - dy1;
 
    // Initial difference in positions
    int diff_x = p1.x - p2.x;
    int diff_y = p1.y - p2.y;
    //cout << rel_dx << " " << rel_dy << " " << diff_x << " " << diff_y << endl ;
    if (rel_dx != 0 && diff_x % rel_dx == 0) {
        time = diff_x / rel_dx;
        if (time >= 0 && diff_y == time * rel_dy) {
            return true;
        }
    } else if (rel_dy != 0 && diff_y % rel_dy == 0) {
        time = diff_y / rel_dy;
        if (time >= 0 && diff_x == time * rel_dx) {
            return true;
        }
    } else if (rel_dx == 0 && rel_dy == 0) {  
        if (diff_x == 0 && diff_y == 0) {
            time = 0;
            return true;
        }
    }
 
    // No intersection found
    return false;
}
 
 
 
int n ;
vector < pair < int , pair < int , int > > > v ;
int ds[ N ] ;
char c[ N ] ;
 
 
void solve5000(){
	
	FOR( i , n ){
		for( int j = i + 1 ; j < n ; j ++ ){
			// check if they coincide 
			if( c[ i ] == c[ j ] ) continue ; 
			int time = -1 ; 
			if( willIntersect(val[ i ], c[ i ], val[ j ], c[ j ], time) ){
				time = abs( time ) ; 
				v.pb( { time , { i , j } } ) ;
		//		cout << i << " " << j << " time " << time << endl;
			}
		}
	}
	
	sort( v.begin() , v.end() ) ;
	
	for( auto x : v ){
		if( ds[ x.s.f ] != -1 && ds[ x.s.s ] != -1 ) continue ; 
		if( ds[ x.s.f ] == -1 && ds[ x.s.s ] == -1 ){
		 	ds[ x.s.f ] = x.f ; 
		 	ds[ x.s.s ] = x.f ; continue ; 
		}
		if( ds[ x.s.f ] == -1 ){
			if( ds[ x.s.s ] == x.f ) ds[ x.s.f ] = x.f ; 
		} 
		else{
			if( ds[ x.s.f ] == x.f ) ds[ x.s.s ] = x.f ; 			
		}
		
	}
	FOR( i , n ){
		if( ds[ i ] == -1 ) cout << i + 1 << " " ;
	}
	return ; 
	
}



map < int , set < pair < int , int > > > se ;
set < pair < int , pair < int , int > > > ss ;  
void solve(){
	cin >> n ;
	FOR( i , n ) cin >> val[ i ].x >> val[ i ].y >> c[ i ] ; 
	FOR( i , n ) ds[ i ] = -1 ; 
	
	if( n <= 5000 ){
	  solve5000() ; 
	  return ;
	}
	
	// else go for moreee
	
	int mmx = 1e9 + 1 ; 
	
	vector < pair < int , pair < int , int > > > vv ; 
	FOR( i , n ){
		if( c[ i ] == 'S' ){
			ss.insert( { val[ i ].x , { - val[ i ].y , i } } ) ;
		}
		else{
			vv.pb( { val[ i ].x , { val[ i ].y , i } } ) ; 
			
//			int poss = val[ i ].y - ( mmx - val[ i ].x ) ; 
//			se[ poss ].insert( { val[ i ].y , i } ) ;
		}	
	}
	
	sort( vv.begin() , vv.end() ) ; 
	int i = 0 ; 
	while( true ){
		if( ss.size() == 0 ) break ;
		pair < int , pair < int , int > > p ;
		p = *ss.begin() ; ss.erase( ss.begin() ) ;
		int x = p.f , y = -p.s.f , indx = p.s.s ; 
		
		while( true ){
			if( i == vv.size() ) break ;
			if( vv[ i ].f > x ) break ;
			int poss = vv[ i ].s.f - ( mmx - vv[ i ].f ) ; 
			se[ poss ].insert( { vv[ i ].s.f , vv[ i ].s.s } ) ;
			i ++ ; 
		}
		
		
		int nec = y - ( mmx - x ) ; 
		
		if( se[ nec ].size() == 0 ) continue ;
		
		pair < int , int > pp ;
		pp = *se[ nec ].begin() ; 
		se[ nec ].erase( se[ nec ].begin() ) ; 
		
		ds[ pp.s ] = 1 ;
		ds[ indx ] = 1 ;
	}
	
	
	FOR( i , n ){
		if( ds[ i ] == -1 ) cout << i + 1 << " " ;
	}	
}
signed main() {
   ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
   int t = 1 ; // cin >> t ;
   while( t -- ){
   	 solve() ;
   }
 
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:164:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |    if( i == vv.size() ) break ;
      |        ~~^~~~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 12 / 12
• Subtask 3: 8 / 8
• Subtask 4: 11 / 11
• Subtask 5: 9 / 9
• Subtask 6: 30 / 30
• Subtask 7: 0 / 24