Submission #1227195

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227195		pravcoder	Naval battle (CEOI24_battle)	C++20	76 / 100	720 ms	41664 KiB

Main

#include <bits/stdc++.h>
#include <iostream>
#include <queue>
#include <set>
using namespace std;

#define pb push_back
#define mp make_pair
#define rept(i, a, b) for (int i = a; i < b; i++)
#define rep(i, n) for (int i = 0; i < n; i++)
#define vec vector
#define all(x) (x).begin(), (x).end()
#define pq priority_queue

typedef long long ll;
typedef vec<int> vi;
typedef vec<vi> v2i;
typedef pair<ll, ll> pl;
typedef pair<int, int> pi;
typedef vec<pl> vpl;
typedef vec<pi> vpi;
typedef vec<bool> vb;
typedef pq<pair<pair<int, pi>, pi>> qpi;
typedef pq<int> qi;

//sub 1-6

ll ct(pl c1, pl c2, pi d1, pi d2) {
	if (d1==d2) return 0;
	pi rel = {d1.first - d2.first, d1.second - d2.second};
	//cout << "calculating collide time" << endl;
	ll t = max(abs(c2.first - c1.first), abs(c2.second - c1.second)) / max(abs(rel.first), abs(rel.second));
	//cout << "t = " << t << endl;
	if (c1.first + t*rel.first == c2.first && c1.second + t*rel.second == c2.second) return max(t, (ll)0);
	return 0;
}

void sub1(int n, vpl& c, vpi& d) {
	if (ct(c[0], c[1], d[0], d[1]) == 0) {
		cout << "1 2\n";
	}
}

void sub5(int n, vpl& c, vpi& d) {
	qpi q;
	rep(i, n-1) {
		rept(j, i+1, n) {
			int t = ct(c[i], c[j], d[i], d[j]);
			if (t!=0) {
				q.push({{-t, {c[i].first+t*d[i].first, c[i].second+t*d[i].second}}, {i, j}});
			}
		}
	}
	vb s(n, true);
	while (!q.empty()) {
		auto t = q.top().first;
		//cout << "at time " << -t.first << ": ";
		set<int> sh;
		while (!q.empty() && q.top().first == t) {
			int i = q.top().second.first, j = q.top().second.second;
			q.pop();
			if (s[i]) sh.insert(i);
			if (s[j]) sh.insert(j);
		}
		if (sh.size() > 1) {
			while (!sh.empty()) {
				//cout << *sh.begin() << " ";
				s[*sh.begin()] = false;
				sh.erase(sh.begin());
			}
		}// else cout << *sh.begin();
		//cout << endl;
	}

	rep(i, n) {
		if (s[i]) cout << i+1 << " ";
	} cout << "\n";
}

void sub6(int n, vpl& c, vpi& d) {
	pq<pair<pi, int>> q;
	rep(i, n) {
		q.push({{-(c[i].first + c[i].second), -c[i].first}, i});
	}
	vb s(n, true);
	while (!q.empty()) {
		int ln = q.top().first.first;
		//cout << "\nline number " << -ln << ": ";
		vi l;
		l.reserve(q.size());
		while (!q.empty() && q.top().first.first == ln) {
			l.pb(q.top().second);
			//cout << q.top().second << " ";
			q.pop();
		}// cout << endl;
		vi e;
		e.reserve(l.size());
		for (auto i : l) {
			if (d[i].first == 1) {
				e.pb(i);
				//cout << "added " << i << " to queue" << endl;
			} else if (e.size() > 0) {
				s[i] = false;
				s[e[e.size()-1]] = false;
				//cout << "crash of " << i << " and " << e[e.size()-1] << endl;
				e.pop_back();
			}
		}
	}

	rep(i, n) {
		if (s[i]) cout << i+1 << " ";
	} cout << "\n";
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	cin >> n;

	vpl c(n);
	vpi d(n);

	rep(i,n) {
		char dir;
		cin >> c[i].first >> c[i].second >> dir;
		if (dir=='N') d[i] = {0, -1};
		if (dir=='E') d[i] = {1, 0};
		if (dir=='S') d[i] = {0, 1};
		if (dir=='W') d[i] = {-1, 0};
	}

	//cout << "done input" << endl;

	if (n==2) sub1(n, c, d);
	else if (n<=5000) sub5(n,c,d);
	else sub6(n, c, d);

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