Submission #1068412

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068412		lollipop	Naval battle (CEOI24_battle)	C++17	46 / 100	3086 ms	791096 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 solve(){
	cin >> n ;
	
	
	
	FOR( i , n ) cin >> val[ i ].x >> val[ i ].y >> c[ i ] ; 
	FOR( i , n ) ds[ i ] = -1 ; 
	
	
	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 ; 
}
signed main() {
   ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
   int t = 1 ; // cin >> t ;
   while( t -- ){
   	 solve() ;
   }

}

• 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: 0 / 30
• Subtask 7: 0 / 24