Submission #1175533

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175533		MuhammadSaram	Naval battle (CEOI24_battle)	C++20	46 / 100	2103 ms	209436 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[n],y[n];
		char c;
		for (int i=0;i<n;i++)
		{
			cin>>x[i]>>y[i]>>c;
			se[x[i]-y[i]].push_back({x[i],i+1,ty(c)});
		}
		vector<int> ans;
		for (auto [w,v]:se)
		{
			sort(v.begin(),v.end());
			int l=0;
			vector<pair<int,int>> rn;
			for (int i=1;i<v.size();i++)
				if (v[l][2]!=v[i][2])
					rn.push_back({l,i}),l=i;
			rn.push_back({l,n});
			int st=v[0][2];
			for (int i=st;i+1<rn.size();i+=2)
			{
				while (rn[i].first<rn[i].second && rn[i+1].first<rn[i+1].second)
					rn[i].second--,rn[i+1].first++;
				for (int j=rn[i].first;j<rn[i].second;j++)
					ans.push_back(v[j][1]);
				for (int j=rn[i+1].first;j<rn[i+1].second;j++)
					ans.push_back(v[j][1]);
			}
		}
		for (int i:ans)
			cout<<i<<' ';
		cout<<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: 0 / 30
• Subtask 7: 0 / 24