Submission #1137576

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137576		UmairAhmadMirza	Naval battle (CEOI24_battle)	C++20	76 / 100	1487 ms	1114112 KiB

Main

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

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

char d[N];
int dx[4]={0,0,1,-1};
int dy[4]={-1,1,0,0};
map<char,int> mp;
int x[N];
int y[N];
bool sink[N];
vector<pair<int,int>> dia[N];

void solve1(int n){
	map<int,int> mp;
	int c=0;
	for (int i = 0; i < n; ++i){
		if(mp[x[i]+y[i]]==0){
			mp[x[i]+y[i]]=++c;
		}
		dia[mp[x[i]+y[i]]].push_back({x[i],i});
	}
	for (int k = 1; k <=c; ++k){
		sort(dia[k].begin(), dia[k].end());
		vector<int> stk;
		for(auto[xx,i]:dia[k]){
			if(d[i]=='S')
				stk.push_back(i);
			else{
				if(stk.size()==0)
					continue;
				sink[i]=1;
				sink[stk.back()]=1;
				stk.pop_back();
			}
		}
	}
	for(int i=0;i<n;i++)
		if(sink[i]==0)
			cout<<i+1<<endl;
	// return;
}

signed main(){
	int n;
	cin>>n;
	// bool b=0;
	mp['W']=0;
	mp['E']=1;
	mp['S']=2;
	mp['N']=3;
	bool b=1;
	for (int i = 0; i < n; ++i){
		cin>>y[i]>>x[i]>>d[i];
		if(d[i]=='N' || d[i]=='W')
			b=0;
	}
	if(b){
		solve1(n);
		return 0;
	}
	// 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]=='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){
			if(x[vv[1]]+(dx[mp[d[vv[1]]]]*vv[0])!=x[vv[2]]+(dx[mp[d[vv[2]]]]*vv[0]) || y[vv[1]]+(dy[mp[d[vv[1]]]]*vv[0])!=y[vv[2]]+(dy[mp[d[vv[2]]]]*vv[0]))
				continue;
			rem.push_back(vv[1]);
			rem.push_back(vv[2]);
		}
	}
	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: 12 / 12
• Subtask 3: 8 / 8
• Subtask 4: 11 / 11
• Subtask 5: 9 / 9
• Subtask 6: 30 / 30
• Subtask 7: 0 / 24