Submission #1134408

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134408		Alihan_8	Naval battle (CEOI24_battle)	C++20	36 / 100	2118 ms	198968 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
#define size(x) (int)(x).size()
#define int long long

typedef pair <int,int> pii;

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
	bool flag = false;
	if ( u > v ){
		u = v; flag |= true;
	}
	return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
	bool flag = false;
	if ( u < v ){
		u = v; flag |= true;
	}
	return flag;
}

const int inf = 1e12;

int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
    
    int n; cin >> n;
    
    vector <int> x(n), y(n), t(n);
    
    for ( int i = 0; i < n; i++ ){
		char t_; cin >> x[i] >> y[i] >> t_;
		
		swap(x[i], y[i]);
		
		if ( t_ == 'N' ) t[i] = 0;
		if ( t_ == 'S' ) t[i] = 1;
		if ( t_ == 'W' ) t[i] = 2;
		if ( t_ == 'E' ) t[i] = 3;
	}
	
	map<int,set<pii>> mp[4][4];
	
	vector <int> s(n), d(n);
	
	for ( int i = 0; i < n; i++ ){
		s[i] = x[i] + y[i];
		d[i] = x[i] - y[i];
		
		mp[1][3][s[i]].insert({x[i], i});
		mp[2][0][s[i]].insert({x[i], i});
		mp[3][0][d[i]].insert({x[i], i});
		mp[1][2][d[i]].insert({x[i], i});
		mp[1][0][y[i]].insert({x[i], i});
		mp[3][2][x[i]].insert({y[i], i});		
	}
	
	vector <int> dp(n, inf);
	
	priority_queue <ar<int,3>> q;
	
	auto cost = [&](int i, int j){
		return (t[i] ^ t[j]) == 1 ? (abs(x[i] - x[j]) + abs(y[i] - y[j])) / 2 : abs(x[i] - x[j]);
	};
	
	for ( int i = 0; i < 4; i++ ){
		for ( int j = 0; j < 4; j++ ){
			auto &tmp = mp[i][j];
			
			for ( auto &[iv, st]: tmp ){
				auto it = st.begin();
				
				while ( it != st.end() ){
					if ( next(it) == st.end() ) break;
					
					int u = it -> second, v = next(it) -> second;
					
					if ( t[u] == i && t[v] == j ){
						q.push({-cost(u, v), u, v});
					} it = next(it);
				} 
			} 
		}
	}
	
	auto er = [&](int i, int j, int v, int idx){
		auto &st = mp[i][j][v];
		
		auto it = st.lower_bound({(i == 1 && !j) ? y[idx] : x[idx], idx});
		
		if ( it == st.end() || it -> second != idx ) return;
		
		if ( it != st.begin() && next(it) != st.end() ){
			int l = prev(it) -> second, r = next(it) -> second;
			
			if ( t[l] == i && t[r] == j ){
				q.push({-cost(l, r), l, r});
			}
		} st.erase(it);
	};
	
	while ( !q.empty() ){
		auto [val, u, v] = q.top();
		q.pop(); val *= -1;
		
		if ( dp[u] < val || dp[v] < val ) continue;
		
		dp[u] = dp[v] = val;
		
		for ( auto idx: {u, v} ){
			er(1, 3, s[idx], idx);
			er(2, 0, s[idx], idx);
			er(3, 0, d[idx], idx);
			er(1, 2, d[idx], idx);
			er(1, 0, y[idx], idx);
			er(3, 2, x[idx], idx);
		}
	}
	
	for ( int i = 0; i < n; i++){
		if ( dp[i] == inf ) cout << i + 1 << '\n';
	}
	
	cout << '\n';
}

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