Submission #1083061

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083061		mychecksedad	Naval battle (CEOI24_battle)	C++17	100 / 100	1018 ms	104608 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
#define ll long long int
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define en cout << '\n'
const int N = 2e5+1;

int n, tp[N], arr[N][2];
vector<array<int, 3>> a[4]; // 'E', 'W', 'N', 'S'
int to[4][3]={
	{0, 2, 5},
	{1, 3, 5},
	{1, 2, 4},
	{0, 3, 4}
};
int f(int x, int y, int p){
	if(p < 2) return x + y;
	if(p < 4) return x - y;
	if(p == 4) return y;
	return x;
}

bool good(array<int, 3> x, array<int, 3> y){
	if(tp[x[2]] == tp[y[2]]) return false;
	if(x[0] > y[0]) swap(x, y);
	else if(x[0] == y[0]){
		if(x[1] > y[1]) swap(x, y);
	}
	// cout << x[0] << ' ' << x[1] << ' ' << x[2] << '\n';
	// cout << y[0] << ' ' << y[1] << ' ' << y[2] << '\n';
	if(x[1] == y[1]){
		return tp[x[2]] == 3;
	}
	if(x[0] == y[0]){
		return tp[x[2]] == 0;
	}
	if(x[0] + x[1] == y[0] + y[1]){
		return (tp[x[2]] == 3 && tp[y[2]] == 0) || (tp[x[2]] == 1 && tp[y[2]] == 2);
	}
	return (tp[x[2]] == 0 && tp[y[2]] == 2) || (tp[x[2]] == 3 && tp[y[2]] == 1);
}
int calc(array<int, 3> x, array<int, 3> y){
	if(x[0] > y[0]) swap(x, y);
	else if(x[0] == y[0]){
		if(x[1] > y[1]) swap(x, y);
	}
	if(x[1] == y[1]){
		return abs(x[0]-y[0])/2;
	}
	if(x[0] == y[0]){
		return abs(x[1]-y[1])/2;
	}
	return abs(x[0]-y[0]);
}


map<int, set<array<int, 3>>> M[6];
void ext(int i, int j, int idx, priority_queue<array<int, 3>> &Q){
	auto it =	M[i][j].lower_bound(array<int,3>{arr[idx][0], arr[idx][1], idx});
	if(next(it) != M[i][j].end() && it != M[i][j].begin()){
		auto it2 = prev(it);
		auto it3 = next(it);
		if(good((*it2), (*it3))){
			Q.push({-calc((*it2), (*it3)), (*it2)[2], (*it3)[2]});
		}
	}
	M[i][j].erase(it);
}
void solve(){
	cin >> n;
	for(int i = 1; i <= n; ++i){
		int x, y; char c; cin >> x >> y >> c;
		swap(x, y);
		arr[i][0] = x;
		arr[i][1] = y;
		if(c == 'E') a[0].pb({x, y, i}), tp[i] = 0;
		if(c == 'W') a[1].pb({x, y, i}), tp[i] = 1;
		if(c == 'N') a[2].pb({x, y, i}), tp[i] = 2;
		if(c == 'S') a[3].pb({x, y, i}), tp[i] = 3;
	}
	
	// 'E', 'S' / 'N', 'W' / 'E', 'N' / 'W', 'S' / 'N', 'S' / 'E', 'W' 
	for(auto p: a[0]){
		for(int i = 0; i < 3; ++i){
			M[to[0][i]][f(p[0], p[1], to[0][i])].insert(p);
		}
	}
	for(auto p: a[1]){
		for(int i = 0; i < 3; ++i){
			M[to[1][i]][f(p[0], p[1], to[1][i])].insert(p);
		}
	}
	for(auto p: a[2]){
		for(int i = 0; i < 3; ++i){

			// cout << to[2][i] << ' ' << f(p[0], p[1], to[2][i]) << '\n';
			M[to[2][i]][f(p[0], p[1], to[2][i])].insert(p);
		}
	}
	for(auto p: a[3]){
		for(int i = 0; i < 3; ++i){
			// cout << p[0] << ' ' << p[1] << ' ' << p[2] << '\n';
			// cout << to[3][i] << ' ' << f(p[0], p[1], to[3][i]) << '\n';
			M[to[3][i]][f(p[0], p[1], to[3][i])].insert(p);
		}
	}
	vector<bool> ded(n + 1);
	priority_queue<array<int, 3>> Q;

	for(int i = 0; i < 6; ++i){
		for(auto &S: M[i]){
			auto it = S.ss.begin();
			while(next(it) != S.ss.end()){
				auto v = *it;
				auto u = *next(it);
				
				if(good(u, v)){
				// 	cout << v[0] << ' ' << v[1] << ' ' << v[2] << '\n';
				// cout << u[0] << ' ' << u[1] << ' ' << u[2] << '\n';
				// cout << endl; 
					Q.push({-calc(u, v), v[2], u[2]});
				}

				it = next(it);
			}
		}
	}
	// cout << "f" << endl;
	int last = -1;
	vector<int> rem;
	while(!Q.empty() || !rem.empty()){
		if(Q.empty()){
			sort(all(rem));
			rem.erase(unique(all(rem)), rem.end());

			for(int idx: rem){
				// cout << idx << endl;
				int t = tp[idx];
				for(int j = 0; j < 3; ++j){
					ext(to[t][j], f(arr[idx][0], arr[idx][1], to[t][j]), idx, Q);
				}
				ded[idx] = 1;
			}

			rem.clear();
			continue;
		}
		auto P = Q.top();
		Q.pop();
		if(-P[0] != last && !rem.empty()){
			sort(all(rem));
			rem.erase(unique(all(rem)), rem.end());

			for(int idx: rem){
				int t = tp[idx];
				for(int j = 0; j < 3; ++j){
					ext(to[t][j], f(arr[idx][0], arr[idx][1], to[t][j]), idx, Q);
				}
				ded[idx] = 1;
			}

			rem.clear();

			Q.push(P);
			continue;
		}
		if(ded[P[1]] || ded[P[2]]) continue;
		// cout << P[1] << ' ' << P[2] << '\n';
		rem.pb(P[1]);
		rem.pb(P[2]);
		last = -P[0];
	}
	

	for(int i = 1; i <= n; ++i) if(ded[i] == 0) cout << i << '\n';
}

int main() {
	cin.tie(0); ios::sync_with_stdio(0);
	solve();
  return 0;
}

• 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