Submission #1074947

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074947		pawned	Naval battle (CEOI24_battle)	C++17	36 / 100	939 ms	154668 KiB

Main

#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

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

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;

const char nl = '\n';

void fastIO() {
	ios::sync_with_stdio(false);
	cin.tie(0);
}

map<char, int> conv = {{'S', 0}, {'N', 1}, {'E', 2}, {'W', 3}};

int N;

vector<pair<ll, ii>> findDiag(map<ll, vector<pair<ii, ii>>> alld) {
	// set of {{x, y}, {type, id}}
	vector<pair<ll, ii>> badpairs;
	// {dist, {id1, id2}}
	for (pair<ll, vector<pair<ii, ii>>> pr : alld) {
//		cout<<"at "<<pr.fi<<endl;
		sort(pr.se.begin(), pr.se.end());
		int K = pr.se.size();
		vi posX;
		vector<char> dir;	// A = east, B = south
		vi idx;
		for (int j = 0; j < K; j++) {
			posX.pb(pr.se[j].fi.fi);
			if (pr.se[j].se.fi == 2)
				dir.pb('A');
			else
				dir.pb('B');
			idx.pb(pr.se[j].se.se);
		}
/*		cout<<"K: "<<K<<endl;
		cout<<"dir: ";
		for (char c : dir)
			cout<<c<<" ";
		cout<<endl;
		cout<<"idx: ";
		for (int x : idx)
			cout<<x<<" ";
		cout<<endl;*/
		// remove all consec
		stack<ii> q;	// all existing A ids, most recent on top
		// {id, pos}
		for (int j = 0; j < K; j++) {
			if (dir[j] == 'A') {
				q.push({idx[j], j});
			}
			else {
				if (!q.empty()) {
					ii x = q.top();
					q.pop();
//					cout<<"removed "<<x<<" "<<idx[j]<<endl;
					badpairs.pb({abs(posX[x.se] - posX[j]), {x.fi, idx[j]}});
				}
			}
		}
	}
	return badpairs;
}

vector<pair<ll, ii>> findLine(map<ll, vector<pair<ll, ii>>> alld) {
	// set of {x, {type, id}}
	vector<pair<ll, ii>> badpairs;
	// {dist, {id1, id2}}
	for (pair<ll, vector<pair<ll, ii>>> pr : alld) {
//		cout<<"at "<<pr.fi<<endl;
		sort(pr.se.begin(), pr.se.end());
		int K = pr.se.size();
		vi posX;
		vector<char> dir;	// A = increasing, B = decreasing
		vi idx;
		for (int j = 0; j < K; j++) {
			posX.pb(pr.se[j].fi);
			if (pr.se[j].se.fi == 0)
				dir.pb('A');
			else
				dir.pb('B');
			idx.pb(pr.se[j].se.se);
		}
/*		cout<<"K: "<<K<<endl;
		cout<<"dir: ";
		for (char c : dir)
			cout<<c<<" ";
		cout<<endl;
		cout<<"idx: ";
		for (int x : idx)
			cout<<x<<" ";
		cout<<endl;*/
		// remove all consec
		stack<ii> q;	// all existing A ids, most recent on top
		// {id, pos}
		for (int j = 0; j < K; j++) {
			if (dir[j] == 'A') {
				q.push({idx[j], j});
			}
			else {
				if (!q.empty()) {
					ii x = q.top();
					q.pop();
//					cout<<"removed "<<x<<" "<<idx[j]<<endl;
					badpairs.pb({abs(posX[x.se] - posX[j]) / 2, {x.fi, idx[j]}});
				}
			}
		}
	}
	return badpairs;
}

int main() {
	fastIO();
	cin>>N;
	vector<pair<int, ii>> ships;
	// {type, {x, y}}
	map<ll, vector<pair<ii, ii>>> alldSE;	// all on diagonal x+y=i, going down
	// set of {{x, y}, {type, id}}
	map<ll, vector<pair<ii, ii>>> alldSW;
	map<ll, vector<pair<ii, ii>>> alldNE;
	map<ll, vector<pair<ii, ii>>> alldNW;
	map<ll, vector<pair<ll, ii>>> alldNS0;	// even y pos
	map<ll, vector<pair<ll, ii>>> alldNS1;	// odd y pos
	// all on same x value, set of {y, {type, id}}
	map<ll, vector<pair<ll, ii>>> alldEW0;
	map<ll, vector<pair<ll, ii>>> alldEW1;
	for (int i = 0; i < N; i++) {
		ll x, y; char d;
		cin>>x>>y>>d;
		ships.pb({conv[d], {x, y}});
		if (conv[d] == 0) {	// south
			alldSE[x + y].pb({{x, y}, {0, i}});
			alldSW[-x + y].pb({{-x, y}, {0, i}});
		}
		if (conv[d] == 2) {	// east
			alldSE[x + y].pb({{x, y}, {2, i}});
			alldNE[x - y].pb({{x, -y}, {2, i}});
		}
		if (conv[d] == 1) {	// north
			alldNE[x - y].pb({{x, -y}, {0, i}});
			alldNW[-x - y].pb({{-x, -y}, {0, i}});
		}
		if (conv[d] == 3) {	// west
			alldSW[-x + y].pb({{-x, y}, {2, i}});
			alldNW[-x - y].pb({{-x, -y}, {2, i}});
		}
		if (conv[d] == 0 || conv[d] == 1) {	// S or N
			if (y % 2 == 0)
				alldNS0[x].pb({y, {conv[d], i}});
			else
				alldNS1[x].pb({y, {conv[d], i}});
		}
		if (conv[d] == 2 || conv[d] == 3) {	// E or W
			if (x % 2 == 0)
				alldEW0[y].pb({x, {conv[d] - 2, i}});
			else
				alldEW1[y].pb({x, {conv[d] - 2, i}});
		}
	}
	vector<vector<pair<ll, ii>>> allv = {findDiag(alldSE), findDiag(alldSW), findDiag(alldNE), findDiag(alldNW), findLine(alldNS0), findLine(alldNS1), findLine(alldEW0), findLine(alldEW1)};
	// then sort all the distances created
/*	for (vector<pair<ll, ii>> v : allv) {
		for (pair<ll, ii> p : v)
			cout<<"("<<p.fi<<", "<<p.se.fi<<", "<<p.se.se<<"); ";
		cout<<endl;
	}*/



	vector<pair<ll, ii>> sink;
	for (vector<pair<ll, ii>> v : allv) {
		for (pair<ll, ii> p : v)
			sink.pb(p);
	}
/*	cout<<"sinking: "<<endl;
	for (pair<ll, ii> p : sink)
		cout<<p.fi<<" "<<p.se.fi<<" "<<p.se.se<<endl;*/
	map<ll, vector<ii>> allr;
	for (pair<ll, ii> p : sink) {
		allr[p.fi].pb(p.se);
	}
	vector<bool> alive(N, true);	// still alive
	for (pair<ll, vector<ii>> pr : allr) {
//		cout<<"at "<<pr.fi<<endl;
		set<int> toremove;
		for (ii p : pr.se) {
			if (alive[p.fi] && alive[p.se]) {
				toremove.insert(p.fi);
				toremove.insert(p.se);
			}
		}
		for (int x : toremove) {
//			cout<<"removed "<<x<<endl;
			alive[x] = false;
		}
	}
//	cout<<"ANSWER: "<<endl;
	for (int i = 0; i < N; i++) {
		if (alive[i])
			cout<<(i + 1)<<endl;
	}
}

• 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