Submission #1175543

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175543		MuhammadSaram	Naval battle (CEOI24_battle)	C++20	76 / 100	2991 ms	209360 KiB

Main

#include <bits/stdc++.h>

using namespace std;

bool ty(char c)
{
	return c=='N' or c=='S';
}

int coll(int x,int y,char c,int x1,int y1,char c1)
{
	if (c==c1) return -1;
	if (ty(c)==ty(c1))
	{
		if (ty(c))
		{
			if (c1=='N')
				swap(y,y1);
			if (x==x1 && y>y1)
				return (y-y1)/2;
			return -1;
		}
		else
		{
			if (c1=='E')
				swap(x,x1);
			if (y==y1 && x<x1)
				return (x1-x)/2;
			return -1;
		}
	}
	if (ty(c1))
		swap(x,x1),swap(y,y1),swap(c,c1);
	if (c=='N')
	{
		if(c1=='E' && x1<x && x-y==x1-y1)
			return x-x1;
		else if(c1=='W' && x1>x && x+y==x1+y1)
			return x1-x;
	}
	else if(c=='S')
	{
		if(c1=='E' && x1<x && x+y==x1+y1)
			return x-x1;
		else if(c1=='W' && x<x1 && x-y==x1-y1)
			return x1-x;
	}
	return -1;
}

int main()
{
	int n;
	cin>>n;
	if (n<=5000)
	{
		int x[n],y[n];
		char c[n];
		for (int i=0;i<n;i++)
			cin>>x[i]>>y[i]>>c[i];
		map<int,vector<pair<int,int>>> edg;
		for (int i=0;i<n;i++)
			for (int j=i+1;j<n;j++)
			{
				int w=coll(x[i],y[i],c[i],x[j],y[j],c[j]);
				if (~w)
					edg[w].push_back({i,j});
			}
		bool det[n]={};
		for (auto [t,v]:edg)
		{
			set<int> se;
			for (auto [i,j]:v)
				if (!det[i] && !det[j])
					se.insert(i),se.insert(j);
			for (int i:se)
				det[i]=1;
		}
		for (int i=0;i<n;i++)
			if (!det[i])
				cout<<i+1<<endl;
	}
	else
	{
		map<int,vector<vector<int>>> se;
		int x,y;
		char c;
		for (int i=0;i<n;i++)
		{
			cin>>x>>y>>c;
			se[x+y].push_back({x,i+1,ty(c)});
		}
		vector<int> ans;
		for (auto [w,v]:se)
		{
			sort(v.begin(),v.end());
			stack<int> st;
			for (int i=0;i<v.size();i++)
				if (v[i][2])
				{
					if (st.empty()) ans.push_back(v[i][1]);
					else st.pop();
				}
				else
					st.push(v[i][1]);
			while (!st.empty())
				ans.push_back(st.top()),st.pop();
		}
		for (int i:ans)
			cout<<i<<endl;
	}
	
	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