Submission #1137524

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137524		UmairAhmadMirza	Naval battle (CEOI24_battle)	C++20	6 / 100	1392 ms	1114112 KiB

Main

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

#define ll long long
int const N=2e5+5;
int const mod=1e9+7;

char d[N];
int x[N];
int y[N];
bool sink[N];

int main(){
	int n;
	cin>>n;
	// bool b=0;
	for (int i = 0; i < n; ++i)
		cin>>y[i]>>x[i]>>d[i];
	// cerr<<"we"<<endl;
	vector<vector<int>> mov;
	for(int i=0;i<n;i++)
		for(int j=i+1;j<n;j++){
			if(d[i]==d[j])
				continue;
			if((d[i]=='E' && d[j]=='W')){
				if(x[i]==x[j] && y[i]<=y[j] && abs(y[i]-y[j])%2==0)
					mov.push_back({abs(y[i]-y[j])/2,i,j});
			}
			else if((d[i]=='W' && d[j]=='E')){
				if(x[i]==x[j] && y[j]<=y[i] && abs(y[i]-y[j])%2==0)
					mov.push_back({abs(y[i]-y[j])/2,i,j});
			}
			else if((d[i]=='S' && d[j]=='N')){
				if(y[i]==y[j] && x[i]<=x[j] && abs(x[i]-x[j])%2==0)
					mov.push_back({abs(x[i]-x[j])/2,i,j});
			}
			else if((d[i]=='N' && d[j]=='S')){
				if(y[i]==y[j] && x[j]<=x[i] && abs(x[i]-x[j])%2==0)
					mov.push_back({abs(x[i]-x[j])/2,i,j});
			}

			else if((d[i]=='E' && d[j]=='S')){
				if(-(x[i]-x[j])==(y[i]-y[j]))
					mov.push_back({abs(x[i]-x[j]),i,j});
			}
			else if((d[i]=='E' && d[j]=='N')){
				if((x[i]-x[j])==(y[i]-y[j]))
					mov.push_back({abs(x[i]-x[j]),i,j});
			}
			else if((d[i]=='W' && d[j]=='S')){
				if((x[i]-x[j])==(y[i]-y[j]))
					mov.push_back({abs(x[i]-x[j]),i,j});
			}
			else if((d[i]=='W' && d[j]=='N')){
				if(-(x[i]-x[j])==(y[i]-y[j]))
					mov.push_back({abs(x[i]-x[j]),i,j});
			}
			else if((d[i]=='S' && d[j]=='E')){
				if(-(x[i]-x[j])==(y[i]-y[j]))
					mov.push_back({abs(x[i]-x[j]),i,j});
			}
			else if((d[i]=='S' && d[j]=='W')){
				if((x[i]-x[j])==(y[i]-y[j]))
					mov.push_back({abs(x[i]-x[j]),i,j});
			}
			else if((d[i]=='N' && d[j]=='E')){
				if((x[i]-x[j])==(y[i]-y[j]))
					mov.push_back({abs(x[i]-x[j]),i,j});
			}
			else if((d[i]=='N' && d[j]=='W')){
				if(-(x[i]-x[j])==(y[i]-y[j]))
					mov.push_back({abs(x[i]-x[j]),i,j});
			}
		}
	sort(mov.begin(), mov.end());
	vector<int> rem;
	int pre=-1;
	for(vector<int> vv:mov){
		if(pre!=vv[0]){
			for(int i:rem)
				sink[i]=1;
			rem.clear();
			pre=vv[0];
		}
		// cout<<vv[0]<<' '<<vv[1]<<' '<<vv[2]<<endl;
		if(sink[vv[1]]==0 && sink[vv[2]]==0){
			rem.push_back(vv[2]);
			rem.push_back(vv[1]);
		}
	}
	for(int i:rem)
		sink[i]=1;
	for(int i=0;i<n;i++)
		if(sink[i]==0)
			cout<<i+1<<endl;

	return 0;
}

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