Submission #1122217

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122217		peacebringer1667	Naval battle (CEOI24_battle)	C++17	46 / 100	3087 ms	795220 KiB

Main

#include<bits/stdc++.h>
#define ll long long
#define ldb long double
#define db double
#define fi first
#define se second
#define sza(a) (int)a.size()
#define pir pair<int,int>
#define pirll pair<ll,ll>
using namespace std;
const int maxn = 2e5 + 5;

struct CTDL{
	int x = 0,y = 0,direction = 0,id = 0;
};

CTDL a[maxn];

void move_ship(CTDL &t){
	if (t.direction == 0) t.y--;
	if (t.direction == 1) t.x++;
	if (t.direction == 2) t.y++;
	if (t.direction == 3) t.x--;
}

int get_direction(const char &c){
    if (c == 'N') return 0;
	if (c == 'E') return 1;
	if (c == 'S') return 2;
	return 3;	
}
void input(int n){
	for (int i = 1 ; i <= n ; i++){
        cin >> a[i].x >> a[i].y;
        
        a[i].id = i;
        char c;
        cin >> c;
        a[i].direction = get_direction(c);
	}
}

int collide(CTDL s1,CTDL s2){
	if (s1.direction > s2.direction) swap(s1,s2);
	
	int x1 = s1.x,y1 = s1.y,d1 = s1.direction,x2 = s2.x,y2 = s2.y,d2 = s2.direction;
	
	if (d1 == d2) return -1;
	
	//N-E collision
	if (d1 == 0 && d2 == 1){
		if (x1 < x2 || y1 < y2) return -1;
		if (y1 - y2 == x1 - x2) return x1 - x2;
		return -1;
	}
	
	//N-S collision
	if (d1 == 0 && d2 == 2){
		if (x1 != x2 || y1 < y2 || (y1 - y2) % 2) return -1;
		return (y1 - y2)/2;
	}
	
	//N-W collision
	if (d1 == 0 && d2 == 3){
		if (x1 > x2 || y1 < y2) return -1;
		if (y1 - y2 == x2 - x1) return y1 - y2;
		return -1;
	}
	
	//E-S collision
	if (d1 == 1 && d2 == 2){
		if (x1 > x2 || y1 < y2) return -1;
		
		if (y1 - y2 == x2 - x1) return y1 - y2;
		return -1;
	}
	
	//E-W collision
	if (d1 == 1 && d2 == 3){
		if (y1 != y2 || x1 > x2 || (x2 - x1) % 2) return -1;
		return (x2 - x1)/2;
	}
	
	//S-W collision
	if (d1 == 2 && d2 == 3){
		if (x1 > x2 || y1 > y2) return -1;
		if (y2 - y1 != x2 - x1) return -1;
		
		return x2 - x1; 
	}
	
	return -1;
}

namespace subtask_3_4_5{
	bool subtask_3_4_5(int n){
		return (n <= 5000);
	}
	
	bool deleted[maxn];
	vector <pair<int,pir>> collision;
	
	void generate_collision(int n){
		for (int i = 1 ; i <= n ; i++)
		  for (int j = i + 1 ; j <= n ; j++){
		      int t = collide(a[i],a[j]);
		      
		      if (t > -1)
		        collision.push_back({t,{i,j}});
		  }
	}
	
	void ship_solve(int n){
		generate_collision(n);
		sort(collision.begin(),collision.end());
		
		int p = 0,N = collision.size();
		while (p < N){
			int nxt = p;
			while (nxt < N && collision[p].fi == collision[nxt].fi) nxt++;
			
			vector <int> to_delete;
			for (int i = p ; i < nxt ; i++){
				int u = collision[i].se.fi,v = collision[i].se.se;
				
				if (deleted[u] || deleted[v]) continue;
				
				if (u == 20 || v == 20) cerr << u << " " << v << " " << collision[p].fi << endl;
				
				to_delete.push_back(u);
				to_delete.push_back(v);
			}
			
			for (int u : to_delete)
			  deleted[u] = 1;
			
			p = nxt;
		}
	}
	
	void solve(int n){
		ship_solve(n);
		
		for (int i = 1 ; i <= n ; i++)
		  if (!deleted[i]) cout << i << "\n";
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
    
//    freopen("NAVAL.inp","r",stdin);
//    freopen("NAVAL.out","w",stdout);
    
    int n;
    cin >> n;
    input(n);
	
	subtask_3_4_5::solve(n);
	
 
	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