Submission #1137645

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137645		ghammazhassan	Naval battle (CEOI24_battle)	C++20	46 / 100	2273 ms	1114112 KiB

Main

// #include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <set>
using namespace std;
#define int long long
#define endl "\n";
const int N=2e5+5;
const int M=1e9+7;
void solve()
{
	int n;
	cin >> n;
	vector<pair<int,int>>a(n);
	vector<char>s(n);
	for (int i=0;i<n;i++){
		int d1,d2;
		char r;
		cin >> d1 >> d2 >> r;
		a[i]={d1,d2};
		s[i]=r;
	}
	vector<int>vi(n,1);
	vector<int>di(n,1e10);
	vector<pair<int,pair<int,int>>>op;
	for (int i=0;i<n;i++){
		for (int j=i+1;j<n;j++){
			int x1,y1,x2,y2;
			char s1,s2;
			x1=a[i].first;
			x2=a[j].first;
			y1=a[i].second;
			y2=a[j].second;
			s1=s[i];
			s2=s[j];
			if (s1==s2){
				continue;
			}
			if (s1=='S' and s2=='N'){
				if (y1>y2 or x1!=x2){
					continue;
				}
				op.push_back({abs(y2-y1)/2,{i,j}});
			}
			if (s1=='N' and s2=='S'){
				if (y1<y2 or x1!=x2){
					continue;
				}
				op.push_back({abs(y2-y1)/2,{i,j}});
			}
			if (s1=='E' and s2=='W'){
				if (x1>x2 or y1!=y2){
					continue;
				}
				op.push_back({abs(x2-x1)/2,{i,j}});
			}
			if (s1=='W' and s2=='E'){
				if (x1<x2 or y1!=y2){
					continue;
				}
				op.push_back({abs(x2-x1)/2,{i,j}});
			}

			int o=abs(x1-x2);
			if (s1=='S'){
				y1+=o;
			}
			else if (s1=='N'){
				y1-=o;
			}
			else if (s1=='E'){
				x1+=o;
			}
			else if (s1=='W'){
				x1-=o;
			}

			if (s2=='S'){
				y2+=o;
			}
			else if (s2=='N'){
				y2-=o;
			}
			else if (s2=='E'){
				x2+=o;
			}
			else if (s2=='W'){
				x2-=o;
			}
			if (x1!=x2 or y1!=y2){
				continue;
			}
			op.push_back({o,{i,j}});
		}
	}
	sort(op.begin(),op.end());
	int k=op.size();
	for (int i=0;i<k;i++){
		int e=op[i].second.first;
		int f=op[i].second.second;
		int r=op[i].first;
		// cout << e << " " << f << " " << r << endl;
		if (r<=di[e] and r<=di[f]){
			vi[e]=0;
			vi[f]=0;
			di[e]=r;
			di[f]=r;
		}
	}
	for (int i=0;i<n;i++){
		if (vi[i]){
			cout << i+1 << endl;
		}
	}
}		


signed main()
{

    ios::sync_with_stdio(0);//DO NOT USE IN INTERACTIVE
    cin.tie(0), cout.tie(0);//DO NOT USE IN INTERACTIVE
    cout << fixed<<setprecision(9);
    int t=1;
    // cin >> t;
    for (int _=1;_<=t;_++){
    	solve();
    }
}

• 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