Submission #1040981

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040981		Lucpp	Naval battle (CEOI24_battle)	C++17	100 / 100	725 ms	133356 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pl = pair<long, long>;
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)size(x)
constexpr ll inf = 1e18;
map<char, pair<int, int>> vecs = {{'N', {0, -1}}, {'E', {1, 0}}, {'S', {0, 1}}, {'W', {-1, 0}}};

int main(){
	cin.tie(0)->sync_with_stdio(false);
	int n;
	cin >> n;
	vector<ll> x(n), y(n);
	vector<char> dir(n);
	map<ll, vector<int>> ES, EW, EN, SN, WS, WN;
	for(int i = 0; i < n; i++){
		cin >> x[i] >> y[i] >> dir[i];
		ll s = x[i], t = y[i];
		if(dir[i] == 'E'){
			ES[s+t].push_back(i);
			EW[t  ].push_back(i);
			EN[s-t].push_back(i);
		}
		if(dir[i] == 'S'){
			ES[s+t].push_back(i);
			SN[s  ].push_back(i);
			WS[s-t].push_back(i);
		}
		if(dir[i] == 'W'){
			WN[s+t].push_back(i);
			EW[t  ].push_back(i);
			WS[s-t].push_back(i);
		}
		if(dir[i] == 'N'){
			WN[s+t].push_back(i);
			SN[s  ].push_back(i);
			EN[s-t].push_back(i);
		}
	}
	vector<list<int>> lines;
	vector<vector<pair<list<int>::iterator, int>>> ptr(n);
	priority_queue<tuple<ll, int, int>> pq;
	auto calcTime = [&](int i, int j){
		if(dir[i] == dir[j]) return inf;
		auto [ivx, ivy] = vecs[dir[i]];
		auto [jvx, jvy] = vecs[dir[j]];
		ll vx = ivx - jvx, vy = ivy - jvy;
		ll dx = x[j] - x[i], dy = y[j] - y[i];
		ll factor = 0;
		if(vx != 0) factor = dx / vx;
		else factor = dy / vy;
		assert(vx * factor == dx && vy * factor == dy);
		if(factor < 0) return inf;
		else return factor;
	};
	auto init = [&](map<ll, vector<int>>& mp, function<ll(int)> f){
		for(auto &[_, v] : mp){
			sort(all(v), [&](int a, int b){return f(a) < f(b);});
			lines.push_back(list<int>(all(v)));
			int prv = -1;
			for(auto it = lines.back().begin(); it != lines.back().end(); it++){
				ptr[*it].emplace_back(it, sz(lines)-1);
				if(prv != -1) pq.emplace(-calcTime(prv, *it), prv, *it);
				prv = *it;
			}
		}
	};
	init(ES, [&](int i){return x[i];});
	init(EW, [&](int i){return x[i];});
	init(EN, [&](int i){return x[i];});
	init(SN, [&](int i){return y[i];});
	init(WS, [&](int i){return x[i];});
	init(WN, [&](int i){return x[i];});
	vector<ll> killed(n, inf);
	auto remove = [&](int r){
		for(auto [it, ind] : ptr[r]){
			int i = -1, j = -1;
			if(it != lines[ind].begin())
				i = *prev(it);
			if(next(it) != lines[ind].end())
				j = *next(it);
			if(i != -1 && j != -1)
				pq.emplace(-calcTime(i, j), i, j);
			lines[ind].erase(it);
		};
	};
	while(!pq.empty()){
		auto [t, i, j] = pq.top(); pq.pop();
		t = -t;
		if(t == inf) break;
		if(killed[i] < t || killed[j] < t) continue;
		if(killed[i] == inf) remove(i);
		if(killed[j] == inf) remove(j);
		killed[i] = killed[j] = t;
	}
	for(int i = 0; i < n; i++){
		if(killed[i] == inf) cout << (i+1) << "\n";
	}
}

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