Submission #1137535

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137535		Faisal_Saqib	Naval battle (CEOI24_battle)	C++20	20 / 100	774 ms	580 KiB

Main

//
// Created by faisal-saqib on 10:22 AM 1/20/25.
//
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
using namespace std;
const int N=5e3+10;
struct  {
	long long x,y;
	char d;
} ship[N];
int main() {
	int n;
	cin>>n;
	for(int i=0;i<n;i++) {
		cin>>ship[i].x>>ship[i].y>>ship[i].d;
		// ship[i].x=1e9-ship[i].x;
		// ship[i].y=1e9-ship[i].y;
	}
	bool subtask5=0,subtask1=1;
	if (subtask1) {
		bool alive[n+1]={1};
		for (int i=0;i<n;i++)alive[i]=1;
		int MX=2e5;
		for (int t=1;t<=MX;t++) {
			map<pair<long long,long long>,int>mp;
			for (int i=0;i<n;i++) {
				if (!alive[i])continue;
				if (ship[i].d=='N') {
					ship[i].y--;
				}else if (ship[i].d=='S') {
					ship[i].y++;
				}else if (ship[i].d=='E') {
					ship[i].x++;
				}
				else {
					ship[i].x--;
				}
				if (mp.find({ship[i].x,ship[i].y})==mp.end()) {
					mp[{ship[i].x,ship[i].y}]=i;
				}
				else {
					alive[i]=0;
					alive[mp[{ship[i].x,ship[i].y}]]=0;
				}
			}
		}
		for (int i=0;i<n;i++)if(alive[i])cout<<i+1<<endl;;
	}
	// Subtask 1-5
	if (subtask5) {
		vector<vector<int>> col;
		for(int i=0;i<n;i++)
		{
			for(int j=i+1;j<n;j++)
			{
				// if(i==j)continue;

				if (ship[i].d == 'N' && ship[j].d == 'S') {
					if (ship[i].x == ship[j].x && ship[i].y > ship[j].y) {
						int time = (ship[i].y - ship[j].y) / 2;
						if ((ship[i].y - ship[j].y) % 2 == 0) {
							col.push_back({time, i, j});
						}
					}
				} else if (ship[i].d == 'S' && ship[j].d == 'N') {
					if (ship[i].x == ship[j].x && ship[i].y < ship[j].y) {
						int time = (ship[j].y - ship[i].y) / 2;
						if ((ship[j].y - ship[i].y) % 2 == 0) {
							col.push_back({time, i, j});
						}
					}
				} else if (ship[i].d == 'E' && ship[j].d == 'W') {
					if (ship[i].y == ship[j].y && ship[i].x > ship[j].x) {
						int time = (ship[i].x - ship[j].x) / 2;
						if ((ship[i].x - ship[j].x) % 2 == 0) {
							col.push_back({time, i, j});
						}
					}
				} else if (ship[i].d == 'W' && ship[j].d == 'E') {
					if (ship[i].y == ship[j].y && ship[i].x < ship[j].x) {
						int time = (ship[j].x - ship[i].x) / 2;
						if ((ship[j].x - ship[i].x) % 2 == 0) {
							col.push_back({time, i, j});
						}
					}
				} else if (ship[i].d == 'N' && ship[j].d == 'E') {
					int dx = ship[j].x - ship[i].x;
					int dy = ship[i].y - ship[j].y;
					if (dx > 0 && dy > 0 && dx == dy) {
						col.push_back({dx, i, j});
					}
				} else if (ship[i].d == 'E' && ship[j].d == 'N') {
					int dx = ship[i].x - ship[j].x;
					int dy = ship[j].y - ship[i].y;
					if (dx > 0 && dy > 0 && dx == dy) {
						col.push_back({dx, i, j});
					}
				} else if (ship[i].d == 'S' && ship[j].d == 'W') {
					int dx = ship[i].x - ship[j].x;
					int dy = ship[j].y - ship[i].y;
					if (dx > 0 && dy > 0 && dx == dy) {
						col.push_back({dx, i, j});
					}
				} else if (ship[i].d == 'W' && ship[j].d == 'S') {
					int dx = ship[j].x - ship[i].x;
					int dy = ship[i].y - ship[j].y;
					if (dx > 0 && dy > 0 && dx == dy) {
						col.push_back({dx, i, j});
					}
				} //poipopoji
				else if (ship[i].d == 'N' && ship[j].d == 'W') {
					int dx = ship[i].x - ship[j].x;
					int dy = ship[i].y - ship[j].y;
					if (dx > 0 && dy > 0 && dx == dy) {
						col.push_back({dx, i, j});
					}
				} else if (ship[i].d == 'W' && ship[j].d == 'N') {
					int dx = ship[j].x - ship[i].x;
					int dy = ship[j].y - ship[i].y;
					if (dx > 0 && dy > 0 && dx == dy) {
						col.push_back({dx, i, j});
					}
				} else if (ship[i].d == 'S' && ship[j].d == 'E') {
					int dx = ship[i].x - ship[j].x;
					int dy = ship[j].y - ship[i].y;
					if (dx > 0 && dy > 0 && dx == dy) {
						col.push_back({dx, i, j});
					}
				} else if (ship[i].d == 'E' && ship[j].d == 'S') {
					int dx = ship[j].x - ship[i].x;
					int dy = ship[i].y - ship[j].y;
					// cout<<"Hola "<<i<<' '<<j<<' '<<dx<<' '<<dy<<endl;
					if (dx > 0 && dy > 0 && dx == dy) {
						col.push_back({dx, i, j});
					}
				}
			}
		}
		sort(begin(col),end(col));
		// cout<<"ALL collisions:"<<endl;
		// for (auto it:col) {
		// 	cout<<it[0]<<' '<<it[1]<<' '<<it[2]<<endl;
		// }
		// cout<<endl;
		bool alive[n+1]={1};
		for (int i=0;i<n;i++)alive[i]=1;
		for(int i=0;i<col.size();) {
			vector<int> dead;
			int c=0;
			for (int j=i;j<col.size() and col[j][0]==col[i][0];j++) {
				// cout<<"Collision "<<col[i][0]<<' '<<col[i][1]<<' '<<col[i][2]<<endl;
				if (alive[col[j][1]] && alive[col[j][2]]) {
					dead.push_back(col[j][1]);
					dead.push_back(col[j][2]);
				}
				c++;
			}
			for (int j=0;j<dead.size();j++)alive[dead[j]]=0;
			i+=c;
		}
		vector<int> left;
		for (int i=0;i<n;i++)if(alive[i])left.push_back(i);
		for (int i=0;i<left.size();i++)cout<<left[i]+1<<endl;
	}
}

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